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

הערה: כשהך מתבקש להציג דקדוק מותר לך להשתמש בכללים מהצורה   A גם ל-  S A .

(20%) 1 שאלה
א. הצג דקדוק ליארי ימי היוצר את השפה שמקבל האוטומט הסופי, A הבא:

a
a b

a b

ב. בה אוטומט סופי המקבל את השפה שיוצר הדקדוק G ,שכללי הגזירה שלו הם:
S aS bA a b aabA  | |||
A  aS a aabA | |
ג. מהי השפה שיוצר הדקדוק G מסעיף ב? תאר אותה בתמציתיות ובמדוייק.
(20%) 2 שאלה
הצג דקדוק חופשי-הקשר היוצר את השפה הבאה:
i  j  0 ; { | i j k m n L  a b c d e
n  m  0 ;
i  j  n  m  2 ;
4  k  1 }
12
(20%) 3 שאלה
{ | , , ,  1} השפה את היוצר הקשר-חופשי דקדוק הצג    a b c d h i j k i j k h i j k
(20%) 4 שאלה
G ({S, X ,Y, L, M , R, X , X},{0,1,2}, P, S)  😛 וכללי 







M
Y Y
Y Y
MY MY
YR YR
2 2
2 2
1
2 |
LX LX
X X
X X
XM X M
X X
X X
LX L X
YR
LX
S LXMYR











 
 

0 0
1 1
1
1 1
0 0
0


א. מהי השפה (G(L ?
ב. האם היא רגולרית?
ג. האם היא חופשית-הקשר?
(20%) 5 שאלה
😛 וכללי G S ABC XY ab PS  ({ , , , , , },{ , }, , )
(1) S  ABC התחל
(2) AB aAX  a הוסף
(3) AB bAY  b הוסף
(4) Xa aX  a בזוכרך הימי זוז
Xb bX  (5)
Ya aY  (6)
Yb bY  (7)
(8) XC BaC  a הוסף שוב
(9) YC BbC 
(10) AB  
C  (11)
(12 ( Ba aB זוז שמאלה כדי להמשיך בתהליך
bB Bb  (13)
מהי השפה (G(L