מאגר שאלות ותשובות להוראת מודלים חישוביים:

תכונות סגירות של שפות חופשיות הקשר

אתי מנשה

 

שאלה 1

תהיינה L1 ו- L2 השפות הבאות מעל הא"ב {a,b}:

w} מילה מעל הא"ב {a,b}, n³0  ï  L1 = {anbn w∙R (w)

w} מילה מעל הא"ב {a,b}, n³0  ï  L2 = {R(w)∙w bnan

א. הוכח כי L1 ו- L2 חופשיות הקשר.

ב. הוכח כי L2 Ç L1 חופשית הקשר.

 

פתרון

א. ידוע כי השפה n³0} ï L3= { anbn היא חופשית הקשר, וידוע כי השפה

w} מילה מעל הא"ב {a,b}  ï  L4 = {w∙R(w)

היא חופשית הקשר (שתי הטענות מוכחות בספר הלימוד).

מסגירות משפחת השפות חופשיות ההקשר לשרשור נובע כי גם L1=L3∙L4 היא חופשית הקשר ומסגירות משפחת השפות חופשיות ההקשר להיפוך נובע גם כי L2 = R(L1) היא חופשית הקשר.

ב. לא ניתן להשתמש בסגירות לחיתוך כי השפות חופשיות ההקשר אינן סגורות לפעולת החיתוך. אבל ניתן לראות כי L1ÇL2=L4 שהוגדרה לעיל, ואשר ידוע כי היא חופשית הקשר. נסביר זאת (זו אינה הוכחה פורמלית):

ברור כי L4 Í L1ÇL2: כל מילה מהצורה w×R(w) שייכת הן ל-L1 והן ל-L2 עבור n=0.
תהי
w מילה המקיימת  w=anbnw1R(w1) וגם w=R(w2)w2bmam עבור m,n³0 ו- w1, w2 מעל הא"ב {a,b}.

אם m=0 או n=0 אז ברור ש-w מהצורה w∙R(w). לכן נבחן את המקרה בו n,m>0.
במקרה כזה ניתן לראות כי
w חייבת להיות מהצורה (anbn)xanbnan(bnan)x, כאשר n זוגי וגדול מ-1 ו-0£x. מילים מהצורה הזאת הן גם מהצורה w∙R(w). לכן, בכל מקרה בו L2 Ç L1 Î w,  w היא פלינדרום באורך זוגי, כלומר, מהצורה w∙R(w).

 

שאלה 2

תהי L שפה מעל א"ב כלשהו.

שתי שפות L1 ו- L2 נקראות חלוקה של L אם מתקיים Æ= L2 Ç L1 (כלומר L1 ו- L2 זרות) ו-L = L2 È L1.

תהי L שפת כל המילים מעל הא"ב {a,b} ותהיינה L1 ו- L2 חלוקה של L.

ידוע כי L1 חופשית הקשר. האם בהכרח גם L2 חופשית הקשר? הוכח את תשובתך.

 

פתרון

מאחר ש- Æ= L2 Ç L1 ו-L2 È L1 היא שפת כל המילים מעל הא"ב {a,b},

הרי ש-.

אם L1 חופשית הקשר, משלימתה אינה בהכרח חופשית הקשר וניתן לראות דוגמה מתאימה בספר הלימוד בפתרון תרגיל 6.11.

 

שאלה 3

שתי שפות חופשית הקשר L1 ו- L2 תקראנה חופפות-חלקית אם L1ÇL2¹Æ .

תהיינה La, Lb ו- Lc שפות חופשיות הקשר המקיימות את התנאים הבאים:

1. La ו-Lb חופפות חלקית.

2. Lb ו-Lc חופפות חלקית.

האם בהכרח מתקיים ש- Laו-Lc חופפות-חלקית? הוכח את תשובתך.

 

פתרון

הטענה אינה נכונה. הנה דוגמא נגדית מתאימה:

n>0}, Lb={ancm ï n,m ³0}, La={anbm | n,m ³ 0} ï Lc={cn  

 

  ={an ï n³ 0} ≠ Æ Lb Ç  Laולכן La ו-Lb חופפות חלקית

  ={cn | n> 0} ≠ Æ Lc Ç  Lbולכן La ו-Lc חופפות חלקית

אבל LaÇLc=Æ ולכן La ו-Lc אינן חופפות חלקית.

 

חזרה

למאגר החומרים

לאתר מודלים חישוביים