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

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

אסנת אנגלמן, אסתי מאסטראסי, אורנה אברך-שטיין

 

שאלה 1

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

} k³0,n,m, m=k או  n=m L ={anbmck ï

פתרון

שפה זו דומה מאוד לשפה של ויקטוריה צורי, ובהתאם גם הפתרון דומה, אך פשוט יותר.

ניתן להציג את L כך:

k³0},n L1 ={anbnck ï

k³0},n L2 ={anbkck ï

L2 È L1 = L

את L1 ניתן להציג באופן הבא:

  n³0} L3 ={anbn ï

k³0} L4 =  {ck ï

L1 = L3 ×L4

את L2 ניתן להציג באופן הבא:

  n³0} L5 ={an ï

k³0} L6 ={bkck ï

L2 = L5 ×L6

 

L4 ו-L5  רגולריות (אוטומטים מתאימים הם דומים לאלו שניתנו בפתרון בשאלה 2, אך פשוטים יותר: דרוש רק מצב התחלתי יחיד – התחלתי ומקבל – עם מעבר לולאתי, משום שבמקרה זה התנאי הוא n³0 בעוד שבשאלה 2 התנאי הוא n³1) ולכן חופשיות הקשר.

L3 חופשית הקשר (מוכח בספר לתלמיד) וכמוה גם L6 (אוטומט מחסנית עבור L6 ניתן לקבל מאוטומט מחסנית עבור L3 ע"י החלפת כל a ב-b וכל b ב-c). מסגירות משפחת השפות חופשיות ההקשר לשרשור גם L1  ו-L2 חופשיות הקשר ומסגירות משפחת השפות חופשיות ההקשר לאיחוד גם L חופשית הקשר.

 

שאלה 2

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

א.      נסח שפה המייצגת את הכפרים שישרדו את שינוי המשטר.

ב.       הראה כי השפה שניסחת בסעיף א' חופשית הקשר.

 

פתרון

א. השפה המבוקשת היא L, שפת כל המילים מעל הא"ב {a,b,c} כך שמספר האותיות c במילה אינו עולה על מספר האותיות a או שמספר האותיות c במילה אינו עולה על מספר האותיות b. אם נסמן ב-#s(w) את מספר מופעי  σ ב-w אז:

#c(w) £ #b(w)} או L = {w ï #c(w) £ #a(w)

ב. L2 È L1 = L, כאשר L1 ו-L2 מעל הא"ב {a,b,c}:

L1 = {w ï #c(w) £ #a(w)}
L2 = {w ï #c(w) £ #b(w)}

 

נראה כי L חופשית הקשר: אוטומט עבור  L2 מתקבל מאוטומט מחסנית עבור L1 ע"י החלפת כל a ב-b וכל b ב-a. אוטומט עבור L1  דומה מאוד לאוטומט שניתן לשאלה האחרונה של אלה פוק עבור השפה L4. יש כמה הבדלים: צריך להחליף כל 0 ב-c וכל 1 ב-a. המצבים המקבלים יהיו q1 ו-q0. צריך להוסיף בכל מצב לולאה עצמית עם האות b לכל אות אפשרית בראש המחסנית (כולל מחסנית ריקה) שאינה משנה את תוכן המחסנית. מסגירות משפחת השפות חופשיות ההקשר לאיחוד גם L חופשית הקשר.

 

שאלה 3

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

(כלומר, אם L1 חופשית הקשר ו- L2 רגולרית, אז L1×L2 חופשית הקשר).

 

פתרון

L2 רגולרית ולכן בפרט חופשית הקשר וידוע כי השפות חופשיות ההקשר סגורות לשרשור.

 

חזרה

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

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