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

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

איריס ברגורי צור

 

שאלה 1

נתבונן בשפה מעל הא"ב {a,b,c} המכילה את כל המילים שמקיימות לפחות אחד מהתנאים הבאים:

א. המילה היא פלינדרום.

ב. המילה מורכבת משני חלקים, כך שהחלק הראשון אורכו זוגי ומספר האותיות b בו מתחלק ב-3 והחלק השני מכיל מספר אותיות b הגדול ממספר אותיות a שבו.

ג. מספר האותיות a במילה מתחלק ב-4, מספר האותיות b במילה אי-זוגי ואורך המילה זוגי.

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

 

פתרון

נגדיר את השפות הבאות מעל הא"ב {a,b,c} :

      {w פלינדרום ï L1={w  

      {0= ÷wçmod 2 ï L2={w  

      {מספר האותיות b ב-w מתחלק ב-3 ï L3={w  

      {מספר האותיות b ב-w גדול ממספר האותיות a ב-w ï L4={w  

      {מספר האותיות a ב-w מתחלק ב-4 ï L5={w  

      {מספר האותיות b ב-w אי זוגי ï L6={w  

השפה המוגדרת בשאלה היא בדיוק השפה (L1È((L2ÇL3)×L4))È((L2ÇL5)ÇL6).

L5, L2, L3 הן רגולריות (כמובן, יש להראות אוטומטים סופיים שמקבלים אותן) ולכן מסגירות משפחת השפות הרגולריות לפעולת החיתוך נובע כי גם L2ÇL3 ו-L2ÇL5 רגולריות. L6 אף היא רגולרית (שוב, יש להראות אוטומט שמקבל אותה) ושוב מסגירות השפות הרגולריות לחיתוך נקבל כי (L2ÇL5)ÇL6 רגולרית.

שפה רגולרית היא בפרט חופשית הקשר ולכן L2ÇL3 ו- (L2ÇL5)ÇL6 הן חופשיות הקשר. L4 היא חופשית הקשר (ראו פתרון לשאלה האחרונה של אלה פוק, כאשר באוטומט הנבנה שם עבור L4 יש להחליף כל 1 ב-b, כל 0 ב-a, ולהוסיף לכל מצב אפשרי של המחסנית, כולל מחסנית ריקה, מעברים לולאתיים עם האות c שאינם נוגעים במחסנית).

מסגירות משפחת השפות חופשיות ההקשר לפעולת השרשור נקבל כי (L2ÇL3)×L4 חופשית הקשר. L1 היא חופשית הקשר (ראו דוגמה 5.4 בספר לתלמיד). מסגירות משפחת השפות חופשיות ההקשר לפעולת האיחוד נקבל כי L1È((L2ÇL3)×L4) חופשית הקשר ולכן גם (L1È((L2ÇL3)×L4))È((L2ÇL5)ÇL6) חופשית הקשר.

 

חזרה

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

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