אוטומטים ושפות פורמליות

מטלת מחה (ממ”ן) 13
הקורס: 20440 – אוטומטים ושפות פורמליות
חומר הלימוד למטלה: יחידה 4
מספר השאלות: 5 משקל המטלה: 2 קודות
סמסטר: ב2020 מועד אחרון להגשה: 2020.4.28
י.ק
אא שים לב:
מלא בדייקות את הטופס המלווה לממ”ן בהתאם לדוגמה שלפי המטלות.
העתק את מספר הקורס ומספר המטלה הרשומים לעיל.

הערה: אחת הדרכים להוכיח ששפה היא רגולרית, היא ביית אוטומט (או הצגת ביטוי רגולרי).
במקרה שבחרת בדרך זו איך דרש להוכיח שאכן השפה שהאוטומט מקבל (או השפה
שהביטוי יוצר) שווה לשפה המבוקשת.
ואולם, הגדר את האוטומט במדויק, באופן פורמלי, וכן הסבר מדוע הבייה מתאימה
לשפה המבוקשת.
(15%) 1 שאלה
ם”אם דרוםפלי קראת {a,b,c} מעל w מילה R . w  w
הוכח באמצעות למת היפוח ששפת הפלידרומים מעל {c,b,a {איה רגולרית.
(36%) 2 שאלה
הוכח באמצעות תכוות סגירות שהשפות הבאות אין רגולריות:
{a,b} מעל , L1  {bwbwb | w a*} .א
{ | ( )*, ( )*, # ( ) # ( )} .ב 2 L xey x a b y c d x y      a  c {a,b,c,d,e} מעל,
(14%) 3 שאלה
תהי L שפה רגולרית מעל  .יהי A אוטומט סופי דטרמייסטי המקבל את L .
בה באמצעות A אוטומט סופי המקבל את שפת כל המילים שב- L המקיימות: לכל רישא ממש
שלהן, הרישא איה ב- L .
הערה: u היא רישא ממש של v אם”ם u היא רישא של v ,ו- v  u .
(20%) 4 שאלה
תהי L שפה רגולרית מעל  .הוכח שגם השפה הבאה רגולרית:

8

; 112 2 1 … { * | w ww w    nnn Lˆ  w
1  n ;
;   :1  i  n 1,i לכל  i
; * :1  i  n ,i לכל wi 
L }  1
 2 … n n1 
(15%) 5 שאלה
L היא שפה רגולרית. NP היא שפת כל המילים השייכות ל-L שעבורן לא קיים אף פירוק uvw=z ,
uv w L i  0 שלכל כך | v | 0 שעבורו i . 
הוכח או הפרך את הטעה ש-NP רגולרית.