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

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

ויקטוריה צורי

 

שאלה 1

תהי L השפה הבאה מעל הא"ב {a,b,c}:

} j>i) או k>j) וגם  1 L={aibjck ï i,k,j ³

האם L חופשית הקשר? הוכח את תשובתך.

 

פתרון

שאלה זו מתאימה הן לעבודת כיתה והן כשיעורי בית אחרי סיום תהליך הלימוד של פרקים 5 ו-6. השאלה מדגימה בצורה יפה ששימוש בתכונות סגירות ובפירוק שפה נתונה לשפות פשוטות יותר הוא כדאי גם עבור שפות חופשיות הקשר. 

השאלה מתאימה גם למבחן משום שאינה כוללת בנייה טכנית מורכבת שדורשת זמן רב, כי הבנייה שבה מבוססת במידה רבה על פתרון תרגיל 5.14 מספר הלימוד.

ניתן להציג את L באופן הבא:  L1=L1ÈL2 כאשר L1 ו- L2 מעל {a,b,c} :

 

} k>j וגם  1 L1={aibjck ï i,k,j ³

} j>i וגם  1 L2={aibjck ï i,k,j ³

 

את L1 ניתן להציג באופן הבא: L1=L3×L4    כאשר L3 ו- L4 מעל {a,b,c}:

 

L3={ ai | i ³ 1 }

L4={ bjck | k,j ³ 1, k>j }

 

ובדומה, את L2 ניתן להציג באופן הבא: L2=L5×L6  כאשר L5 ו- L6 מעל {a,b,c}:

 

L5={ aibj | i,j ³ 1, j>1 }

L6={ ck | k ³ 1 }

 

L3 ו-L6 רגולריות, כי ניתן לבנות אוטומטים סופיים שמקבלים אותן. זהו אוטומט עבור L3:

 

 

ואוטומט עבור L6 מתקבל ממנו ע"י החלפת כל a ב-c. מאחר שהשפות הרגולריות הן בפרט חופשיות הקשר, הרי ש-L3 ו-L6 חופשיות הקשר. L5 היא בדיוק השפה שהוצגה בתרגיל 5.14 בספר לתלמיד והיא לכן חופשית הקשר. L4 אף היא חופשית הקשר – ניתן לקבל אוטומט מחסנית שמקבל אותה מאוטומט המחסנית שמקבל את L5 ע"י החלפת כל a  ב-b וכל b ב-c.

מסגירות משפחת השפות חופשיות ההקשר לפעולת השרשור גם L1=L3×L4 ו- L2=L5×L6 הן חופשיות הקשר, ומסגירות משפחת השפות חופשיות ההקשר לפעולת האיחוד גם   L1ÈL2 חופשית הקשר.

 

חזרה

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

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