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

בעיות משולבות

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

 

שאלה 1הוכחת אי רגולריות + בניית אוטומט מחסנית

נתונה השפה מעל הא"ב {a,b,c,d}

L={atbmcpdk½t³m, p≠k, m,p,k³0}

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

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

 

פתרון

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

נסתכל בקבוצת המילים W={at½t>0}. נראה שעל כל מילה בקבוצה W מגיע A למצב שונה.

נניח שקיימות בקבוצה שתי מילים aj, ai כך ש: i>j>0 ו-A מגיע על ai ו-aj לאותו מצב q.

נסתכל על המילה  aibj+1c.

מילה זו שייכת ל-L  (j<i ולכן i³j+1 ו- 1=p≠k=0). ולכן קריאת הסיפא bj+1c מובילה את האוטומט מהמצב q למצב מקבל.

אבל מכאן נובע שאוטומט זה מקבל גם את המילה ajbj+1c, למרות שמילה זו אינה שייכת ל-L (הערך j אינו גדול או שווה לערך j+1).

הגענו לסתירה ולכן בהכרח האוטומט A מגיע למצב שונה על כל מילה ב-W.

מאחר ש-W אינסופית, נובע מכך של-A אינסוף מצבים בסתירה להיותו אוטומט סופי.

לכן הנחת השלילה הראשונה שגויה ומכאן L אינה רגולרית.

ניתן להוכיח גם בעזרת הקבוצה האינסופית W2={a2cp½p>0}:

אם נניח שקיימות בקבוצה זו שתי מילים a2ci, a2cj כך ש- i≠j ו-A מגיע על שתיהן לאותו מצב q, ונתבונן במילה a2cidj , אז מכך שהמילה  a2cidj בשפה (כי 2³0=m ו- i≠j) נובע שהאוטומט A מגיע מהמצב q עם dj למצב מקבל. אבל מכאן נובע שהוא מקבל גם את המילה  a2cjdj שאינה בשפה כי לא מתקיים j=k¹p=j. לכן גם הקבוצה W2 מחייבת מצב שונה לכל מילה – כלומר אינסוף מצבים.

 

ב. השפה חופשית הקשר. נבנה אוטומט מחסנית שמקבל אותה. האוטומט יפעל על פי האלגוריתם הבא: עם קריאת האותיות a האוטומט ידחוף אותיות A למחסנית ועם קריאת אותיות b ישלוף מהמחסנית אותיות A עד להתרוקנותה או עד שמסתיימות האותיות b, אך לא יסכים לקרוא b מעבר להתרוקנות המחסנית (ולכן יש צורך בסימון תחתית המחסנית). עם קריאת אותיות c שוב ידחוף האוטומט אותיות למחסנית ועם קריאת אותיות d יישלפו האותיות מהמחסנית. בשלב המילוי השני האוטומט יסמן את תחתית המחסנית ולכן, עם קריאת הסימון מספר האותיות d שנקראו שווה למספר האותיות c שנקראו. לפיכך, קריאת הסימון צריכה להעביר את האוטומט למצב שאינו מקבל. קריאת אותיות d נוספות מעבר לשוויון מביאה את האוטומט למצב מקבל.

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

q0 – מצב התחלתי בו נקראות אותיות a.

q1 – המצב שבו נקראות אותיות b.

q2 – המצב שבו נקראות אותיות c.

q3 – המצב שבו נקראות אותיות d ומספר האותיות d שנקראו קטן ממספר האותיות c שנקראו.

q4 – המצב שבו נקראו אותיות d במספר שווה למספר האותיות c שנקראו.

q5 – המצב שבו נקראות אותיות d ומספר האותיות d שנקראו גדול ממספר האותיות c שנקראו.

כל המצבים פרט ל- q4 הם מצבים מקבלים.

האלגוריתם שעומד בבסיסו של האוטומט פשוט למדי, אך לאוטומט מעברים רבים, בגלל מקרי הקצה האפשריים הרבים, כאשר לפחות אחת האותיות חסרה (כלומר t, m, p או k שווים ל-0). לכן הגדרה חליפית של השפה בה נתון m, p, k>0 תפשט את האוטומט באופן משמעותי.

מעברים:

קריאת a ראשונה –

(q0,a,^,q0,S)

קריאת a שניה 

(q0,a,S,q0,SA)

קריאת a שלישית ויותר 

(q0,a,A,q0,AA)

קריאת b ראשונה שאינה מביאה לריקון המחסנית –

(q0,b,A,q1,ε)

קריאת b ראשונה המביאה לריקון המחסנית –

(q0,b,S,q2,ε)

קריאת b שניה ויותר שאינה מביאה לריקון המחסנית – 

(q1,b,A,q1,ε)

קריאת b שניה ויותר המביאה לריקון המחסנית –

(q1,b,S,q2,ε)

קריאת c ראשונה כאשר לא נקראו אותיות a ו-b

(q0,c,^,q2,T)

קריאת c  ראשונה כאשר ההפרש בין מספר האותיות a ומספר האותיות b הוא 1 –

(q0,c,S,q2,ST)

קריאת c ראשונה כאשר ההפרש בין מספר האותיות a ומספר האותיות b עולה על 1 –

(q0,c,A,q2,AT)

קריאת c ראשונה כאשר מספר האותיות a שנקראו שווה למספר האותיות b שנקראו –

(q2,c,^,q2,T)

קריאת c שניה –

(q2,c,T,q2,TB)

קריאת c שלישית ויותר –

(q2,c,B,q2,BB)

קריאת d ראשונה כאשר לא נקראו אותיות a, b ו-c

(q0,d,^,q5,ε)

קריאת d ראשונה כאשר לא נקראו אותיות c ו-b ונקראה אות a אחת –

(q0,d,S,q5,ε)

קריאת d ראשונה כאשר לא נקראו אותיות c ו-b ונקראה יותר מאות a אחת –

(q0,d,A,q5,ε)

קריאת d ראשונה כאשר לא נקראו אותיות c,

וההפרש בין מספר האותיות a שנקראו למספר האותיות b שנקראו עולה על 1 –

 

(q1,d,A,q5,ε)

קריאת d ראשונה כאשר לא נקראו אותיות c,

וההפרש בין מספר האותיות a שנקראו למספר האותיות b שנקראו הוא בדיוק 1 –

 

(q1,d,S,q5,ε)

קריאת d ראשונה כאשר לא נקראו אותיות c,

ומספר האותיות a שנקראו שווה למספר האותיות b שנקראו –

 

(q2,d,^,q5,ε)

קריאת d ראשונה כאשר נקראה בדיוק אות c אחת –

(q2,d,T,q4,ε)

קריאת d ראשונה כאשר נקראה יותר מאות c אחת –

(q2,d,B,q3,ε)

קריאת d שניה ויותר כאשר מספר האותיות d שנקראו קטן ממספר האותיות c שנקראו –

(q3,d,B,q3,ε)

קריאת d שניה ויותר כאשר מספר האותיות d שנקראו שווה למספר האותיות c שנקראו –

(q3,d,T,q4,ε)

קריאת d שניה ויותר כאשר מספר האותיות d שנקראו עולה ב-1 על מספר האותיות c שנקראו,

וההפרש בין מספר האותיות a שנקראו ומספר האותיות b שנקראו עולה על 1 –

 

(q4,d,A,q5,ε)

קריאת d שניה ויותר כאשר מספר האותיות d שנקראו עולה ב-1 על מספר האותיות c שנקראו,

וההפרש בין מספר האותיות a שנקראו ומספר האותיות b שנקראו הוא בדיוק 1 –

 

(q4,d,S,q5,ε)

קריאת d שניה ויותר כאשר מספר האותיות d שנקראו עולה ב-1 על מספר האותיות c שנקראו,

ומספר האותיות a שנקראו שווה למספר האותיות b שנקראו –

 

(q4,d,^,q5,ε)

קריאת d שניה ויותר כאשר מספר האותיות d שנקראו

עולה ב-2 לפחות על מספר האותיות c שנקראו, ובמחסנית נותרה יותר מאות אחת –

 

(q5,d,A,q5,ε)

קריאת d שניה ויותר כאשר מספר האותיות d שנקראו

עולה ב-2 לפחות על מספר האותיות c שנקראו, ובמחסנית נותרה אות אחת –

 

(q5,d,S,q5,ε)

קריאת d שניה כאשר מספר האותיות d שנקראו

עולה ב-2 לפחות על מספר האותיות c שנקראו, והמחסנית כבר ריקה –

 

(q5,d, ^,q5,ε)

 

חזרה

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

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