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

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

אלה פוק

 

שאלה 1

תהי R שפה רגולרית ותהי L שפה חופשית הקשר. נניח כי קיימת שפה T כך שמתקיים T×L=R. כיצד ניתן לאפיין את T?

א. T בהכרח רגולרית.

ב. T בהכרח חופשית הקשר ואינה רגולרית.

ג. T בהכרח חופשית הקשר אך יכולה להיות רגולרית או לא.

ד. אף אחד מהנ"ל.

הצדק את תשובתך באופן מלא.

 

פתרון

ידוע כי השפות חופשיות ההקשר סגורות לפעולת השרשור, כלומר אם T ו-L חופשיות הקשר אז R בהכרח חופשית הקשר אבל אין זה אומר ש-R אינה רגולרית. לכן, סעיף א' אינו נכון: ניתן למצוא דוגמה כך ש- T ו-L חופשיות הקשר, ו-T אינה רגולרית, ושרשורן רגולרי.

למשל 0} T={aibj ï i≠j, i, j ³  ,  0} L={bka ï k≠ℓ, k, ℓ ³ .

אלו הן שפות חופשיות הקשר שאינן רגולריות.

שרשורן T×L הוא השפה 0}-{e, a, b, aba} {aibjak ï i,k,j ³, משום שפרט לארבע המילים e, a, b ו-aba כל מילה מהצורה aibjak ניתן לחלוקה לרישא aibj ולסיפא bka, כך שבכל חלק החזקות שונות זו מזו. {e, a, b, aba} היא סופית ולכן רגולרית. { aibjakïi,k,j³0} גם היא רגולרית (יש להראות אוטומט שמקבל אותה).

ע"פ תרגיל 3.27 השפות הרגולריות סגורות להפרש ולכן גם 0}-{e, a, b, aba} {aibjak ï i,k,j ³ היא שפה רגולרית.

 

גם סעיף ב' אינו נכון. T בוודאי יכולה להיות רגולרית ולכן גם חופשית הקשר.

למשלT={a} ׁ(חופשית הקשר כי היא רגולרית), L={b}, ושרשורן הוא השפה {ab}.

ניתן למצוא דוגמה מתאימה גם עבור L שהיא חופשית הקשר ולא רגולרית.

למשל T={aiïi³0},L={anbmïn¹m, n,m³0} , T×L={anbmïn,m³0}.

 

סעיף ג' גם הוא אינו נכון: {w מעל הא"ב {a,b} ï ww} = T,  L היא שפת כל המילים מעל הא"ב {a,b}.

T אינה חופשית הקשר. L רגולרית ולכן חופשית הקשר והשפה T×L היא שפת כל המילים מעל הא"ב {a,b} כי כל מילה x מעל הא"ב {a,b} ניתנת להצגה כ: ε×ε×x.

לכן התשובה הנכונה היא סעיף ד'.

 

שאלה 2

יהיו { s1, ..., sn} ו- { h1, ..., hm}  שני א"ב, לאו דווקא זרים.

תהי L1 שפה חופשית הקשר מעל הא"ב {s1, ..., sn} ו-L2 שפה חופשית הקשר מעל הא"ב {h1, ..., hm}.

עבור מילה w מעל הא"ב {s1, ..., sn} È {h1, ..., hm}

נסמן ב- w/{s1, ..., sn} את המילה המתקבלת מ-w ע"י השמטת האותיות ב- w שאינן שייכות ל- {s1, ..., sn}

ובדומה, נסמן ב- w/{h1, ..., hm} את המילה המתקבלת מ- w ע"י השמטת האותיות ב- w שאינן שייכות ל- {h1, ..., hm}.

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

A(L1,L2) = { w | {σ1, ..., σn} È {η1, ..., ηm}  מעל הא"ב w,

w / { σ1, ..., σn} Î L1,

w / { η1, ..., ηm} Î L2 }

פתרון

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

קל למדי למצוא דוגמה המראה כי A(L1,L2) אינה בהכרח חופשית הקשר.

נבחר L1={ anbnckïn,k³0} מעל הא"ב {a,b,c} ו- L2={ akbncnïn,k³0}מעל אותו הא"ב.

במקרה זה, כמובן {s1, ..., sn} = {h1, ..., hm}

ולכן לכל מילה w מעל {s1, ..., sn} È {h1, ..., hm} מתקיים w/{s1, ..., sn}=w  ו- w/(h1, ..., hm}=w.

בתנאים אלו:

A(L1,L2) = { w | wÎL2 וגם wÎL1, {a,b,c} מעל הא"ב w }

כלומר

A(L1, L2)=L1ÇL2={ anbncnïn³0}

וזו כידוע שפה שאינה חופשית הקשר.

 

שאלה 3

נתבונן בשפה מעל הא"ב {0,1} אשר כל מילה בה מקיימת לפחות אחד משלושת התנאים הבאים:

1. מתחילה ברצף 001 ומסתיימת ברצף 101.

2. מספר האותיות 1 במילה גדול ממספר האותיות 0 במילה.

3. מתחילה ברצף 101 ומסתיימת ברצף 001.

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

פתרון

ניתן להגדיר את L בעזרת השפות הבאות, כולן מעל הא"ב {0,1}:

L1 = { w | 001 מתחילה ברצף w }

L2 = { w | 101 מתחילה ברצף w }

L3 = { w | 001 מסתיימת ברצף w }

L4 = { w | w ב- 0 גדול ממספר האותיות w ב- 1 מספר האותיות }

עכשיו:

זו השפה שמתאימה לתנאי 1:    (L2) R Ç L1 = L5

זו השפה שמתאימה לתנאי 3:    L3 Ç L2 = L6

ו- L4 כמובן מתאימה לתנאי 2.

L= L5ÈL4ÈL6

L1 רגולרית – הנה אוטומט סופי שמקבל אותה:

 

 

בדומה, גם L2 רגולרית ומתקבלת על ידי האוטומט הבא:

 

 

L3 אף היא רגולרית ומתקבלת ע"י האוטומט הבא:

 

 

מסגירות משפחת השפות הרגולריות לפעולת ההיפוך גם R(L2) רגולרית.

מסגירות משפחת השפות הרגולריות לפעולת החיתוך גם (L2)L5=L1ÇR ו-L6=L2ÇL3 רגולריות ובפרט חופשיות הקשר.

L4 אף היא חופשית הקשר ואוטומט המקבל אותה דומה לאוטומט שמתאים לפתרון תרגיל 5.19 בספר לתלמיד.

יש לאוטומט 3 מצבים:

q0 – המצב ההתחלתי, זוכר כי מספר האותיות a שנקראו שווה למספר האותיות 1 שנקראו.

q1 – זוכר כי מספר האותיות 0 שנקראו קטן ממספר האותיות 1 שנקראו. זהו מצב מקבל.

q2 – זוכר כי מספר האותיות 0 שנקראו גדול ממספר האותיות 1 שנקראו.

א"ב הקלט הוא כמובן {0,1} וא"ב המחסנית הוא {S,A}. קבוצת המעברים היא:

קריאת 0 במצב שוויון בין מספר האותיות 0 שנקראו למספר האותיות 1 שנקראו 

(q0,0,^,q2,S)

קריאת 1 במצב שוויון בין מספר האותיות 0 שנקראו למספר האותיות 1 שנקראו 

(q0,1,^,q1,S)

קריאת 0 כאשר יש עודף של אות 1 אחת 

(q1,0,S,q0,ε)

קריאת 1 כאשר יש עודף של אות 1 אחת 

(q1,1,S,q1,SA)

קריאת 0 כאשר יש עודף של אותיות 1 

(q1,0,A,q1,ε)

קריאת 1 כאשר יש עודף של אותיות 1 

(q1,1,A,q1,AA)

קריאת 0 כאשר יש עודף של אות 0 אחת 

(q2,0,S,q2,SA)

קריאת 1 כאשר יש עודף של אות 0 אחת 

(q2,1,S,q0,ε)

קריאת 0 כאשר יש עודף של אותיות 0 

(q2,0,A,q2,AA)

קריאת 1 כאשר יש עודף של אותיות 0 

(q2,1,A,q2,ε)

 

שימו לב שכאן מספיקות שתי אותיות לא"ב המחסנית, שלא כמו באוטומט שניתן במדריך למורה בפתרון תרגיל 5.19. זאת משום שכאן המצבים q1 ו-q2 זוכרים לאיזה אות יש עודף – 0 או 1 ואילו באוטומט ההוא שימשו לכך האותיות שבראש המחסנית.

מסגירות משפחת השפות חופשיות ההקשר לאיחוד גם L5ÈL4 חופשית הקשר וגם L= (L5ÈL4)ÈL6 חופשית הקשר.

 

חזרה

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

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