אוטומטים ושפות פורמליות
מוסד לימוד | האוניברסיטה הפתוחה |
סוג העבודה | ממ"ן |
מספר ממ"ן | 15 |
מקצוע | מתמטיקה ומדעי המחשב |
קורס | אוטומטים ושפות פורמליות |
מילות מפתח | 15, אוטומטים, ושפות פורמליות, פתרונות ממנים האוניברסיטה הפתוחה |
שנת הגשה | 2020 |
מספר מקורות | 1 |
תקציר העבודה
מטלת מחה (ממ"ן) 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