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

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

(22%) 1 שאלה
הבאה רגולרית:  הן שפות רגולריות מעל  .הוכח באמצעות ביית אוטומט ש- L L2 ו- L1
;
;
n  1
  ,1  i  n ,i לכל  i
{ … | L   1 2  n

}
:ש כך, 1  k  n ,k וקיים , v  L2 קיימת
1 2 1 1 1 (בלבד v היא  1…v… n כל אז n=1 אם (  … k  v k … n  L
(22%) 2 שאלה
עבור השפה הבאה: RL רשמו את מחלקות השקילות של היחס
12 2 L w w u v uv u u v u      { {0,1, 2}* | 0 ; , {1, 2}*; # ( ) # ( ) ; # ( ) | |}
(12%) 3 שאלה
בה אוטומט סופי דטרמייסטי קשיר ומצומצם השקול לאוטומט הסופי הבא:

b a
a b
b a
b b
a a a,b
a,  b
a,b a a a,b
b
b c a
e
f
h
J
d
I
g
10
(22%) 4 שאלה
הוכח באמצעות משפט רוד שהשפה הבאה שמעל {e,d,c,b,a {איה רגולרית:
{ | ( )*, ( )*, # ( ) # ( )} 2 L xey x a d y b c x y      a  b
(22%) 5 שאלה
{ {0,1,2}* | # ( ) # ( )} . M  01*0 -ו L  w 0 w  1 w
אם אפשר רשום ביטוי רגולרי המציין את השפה L/M ,ולא, ציין מהי השפה בכתיב קבוצות

העבודה בקובץ PDF