מטלת מחה (ממ"ן) 17
הקורס: 20440 – אוטומטים ושפות פורמליות
חומר הלימוד למטלה: יחידות 9-8
מספר השאלות: 4 משקל המטלה: 2 קודות
סמסטר: ב2020 מועד אחרון להגשה: 2020.6.23
י.ק
אא שים לב:
מלא בדייקות את הטופס המלווה לממ"ן בהתאם לדוגמה שלפי המטלות.
העתק את מספר הקורס ומספר המטלה הרשומים לעיל.

ההערה המופיעה בתחילת ממ"ן 13 תקפה גם כאן, לגבי שפות חופשיות-הקשר ושפות ליאריות
(עם דקדוקים או אוטומטי-מחסית).

(31%) 1 שאלה
Sigma n i n : n  0 לכל גדיר
i
n
( ) …   


0
. 0 1
הוכח באמצעות למת היפוח שהשפות הבאות אין חופשית-הקשר:
{ | 1} .1 ( ) L  a b n  n Sigma n
L  {wcw | w {a,b}*} .2
(18%) 2 שאלה
L' {0 1 2 3 4 |1 i, j, k} :הקשר-חופשית האי הבאה שהשפה לך תון i j k i j .  
הוכח באמצעות תון זה ובאמצעות תכוות סגירות שהשפה
L {ucv | u,v {a,b}* ; # (u) # (v) ; # (u) # (v)} חופשית   a  a b  b .הקשר -האי
(18%) 3 שאלה
תהי L שפה חופשית-הקשר מעל  .הוכח שגם השפה הבאה חופשית-הקשר:
L  {w  * | uwv  L שעבורם u,v   * קיימים {

(33%) 4 שאלה
L {a bc d | 0 j i} השפה את היוצר הקשר-חופשי דקדוק הצג. 1 j i .   
16
2 .הוכח בהסתמך על חלק 1 שהשפה הבאה חופשית-הקשר:

(1 ) : }
(1 ) : 0 ;
0 ;
{ … | 1 ; ~ 1 2
i
i
n n n m
i i k m n
i i k n
m
L x yx y x yz k k


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