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

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

ריקה רם

 

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

תהי L שפת כל המילים מעל הא"ב {a,b,c} שמתחילות ומסתיימות ברצף מעל הא"ב {a,b} שמכיל לפחות אות a אחת ואות b אחת, וחלקן האמצעי הוא רצף של אותיות c ואחריו רצף של אותיות b שווה לו באורכו.

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

 

פתרון

ניתן להציג את L בעזרת שתי השפות הבאות:

L1 - שפת כל המילים מעל הא"ב {a,b} שמכילות לפחות אות a אחת ואות b אחת.

L2 -  {cnbn½n³0}

  L=L1∙L2∙L1

 

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

 

 

L2 חופשית הקשר.

ניתן לקבל אוטומט מחסנית שמקבל אותה מהאוטומט שנתון בספר עבור השפה {anbn½n³0} על ידי החלפת כל a ב- c.

מסגירות משפחת השפות חופשית ההקשר לשרשור גם L1∙L2 חופשית הקשר ולכן גם ∙L1((L1∙L2  חופשית הקשר.

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

נתבונן בקבוצת המילים האינסופית הבאה -  W={abcn½n³0}.

נניח שקיימות בקבוצה זו שתי מילים abci, abcj כך ש-i≠j והאוטומט מגיע על שתיהן לאותו מצב q.

נתבונן במילה abcjbjab. זו מילה בשפה ולכן מהמצב q האוטומט מגיע למצב מקבל בקוראו את הסיפא bjab. אבל אז גם המילה abcibjab מתקבלת למרות שאינה שייכת לשפה.

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

שימו לב – אם היינו מדביקים את הסיפא bjba אז המילה abcjbjba אכן בשפה, אך ייתכן שגם המילה abcibjba בשפה אם במקרה i+1=j.

 

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

תהי L שפת כל המילים מעל הא"ב {a,b,c} אשר מתחילות ברצף אותיות מעל הא"ב {a,b} שמכיל לפחות אות a אחת ואות b אחת, מסתיימות ברצף אותיות מעל הא"ב {a,c} שמכיל לפחות אות a אחת ואות c אחת, אורך הרצף הפותח שווה לאורך הרצף הסוגר, והחלק האמצעי של המילה הוא רצף אותיות c ואחריו רצף אותיות b שווה לו באורכו.

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

 

פתרון

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

נתבונן בקבוצת המילים האינסופית W={abcn½n³0} ונניח שקיימות בקבוצה זו שתי מילים abci, abcj, i≠j כך שהאוטומט מגיע על שתיהן לאותו מצב q.

נתבונן במילה abcibiac. מילה זו בשפה, ולכן כאשר האוטומט קורא את הסיפא biac במצב q הוא מגיע למצב מקבל. לפיכך הוא מקבל גם את המילה abcjbiac שאינה בשפה.

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

 

L חופשית הקשר. נבנה אוטומט מחסנית לא דטרמיניסטי שמקבל אותה.

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

q0 – מצב התחלתי.

q1 – מצב המציין קריאת הרצף הפותח כאשר נקראה כבר לפחות אות a אחת.

q2 – מצב המציין קריאת הרצף הפותח כאשר נקראה כבר לפחות אות b אחת.

q3 – מצב המציין קריאת הרצף הפותח כאשר נקראו לפחות אות a אחת ואות b אחת.

q4 – מצב המציין קריאת רצף האותיות c בחלקה האמצעי של המילה.

q5 – מצב המציין קריאת רצף האותיות b בחלקה האמצעי של המילה.

q6 – מצב המציין קריאת הרצף הסוגר כאשר נקראה כבר לפחות אות a אחת.

q7 – מצב המציין קריאת הרצף הסוגר כאשר נקראה כבר לפחות אות c אחת.

q8 – מצב המציין קריאת הרצף הסוגר כאשר נקראו לפחות אות c אחת ואות a אחת ואורך הרצף הסוגר קטן מאורך הרצף הפותח.

q9 – מצב המציין קריאת הרצף הסוגר כאשר נקראו לפחות אות c אחת ואות a אחת ואורך הרצף הסוגר שווה לאורך הרצף הפותח.

q9 – הוא המצב המקבל היחיד. א"ב המחסנית הוא {S,A,B}.

קבוצת המעברים:

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

(q0,a,^,q1,S)

קריאת אות ראשונה, והיא b

(q0,b, ^,q2,S)

קריאת אות a שנייה, כאשר עדיין לא נקראו אותיות b

(q1,a,S,q1,SA)

קריאת a שלישית ויותר, כאשר עדיין לא נקראו אותיות b

(q1,a,A,q1,AA)

קריאת b שנייה, כאשר עדיין לא נקראו אותיות a  

(q2,b,S,q2,SA)

קריאת b שלישית ויותר, כאשר עדיין לא נקראו אותיות a

(q2,b,A,q2,AA)

קריאת b ראשונה, כאשר נקראה אות a אחת –

(q1,b,S,q3,SA)

קריאת b ראשונה, כאשר נקראה יותר מאות a אחת 

(q1,b,A,q3,AA)

קריאת a ראשונה, כאשר נקראה b  אחת –

(q2,a,S,q3,SA)

קריאת a ראשונה, כאשר נקראה יותר מאות b  אחת –

(q2,a,A,q3,AA)

קריאת a, כאשר נקראו לפניה לפחות a אחת ולפחותb  אחת –

(q3,a,A,q3,AA)

קריאת b, כאשר נקראו לפניה לפחות a אחת ולפחותb  אחת –

(q3,b,A,q3,AA)

ניחוש כי ה- a הבאה מתחילה את הרצף  הסוגר  של המילה,

וכי החלק  האמצעי ריק 

 

(q3,a,A,q6,ε)

קריאת c ראשונה בחלק האמצעי של המילה –

(q3,c,A,q4,AB)

ניחוש כי ה- c הבאה מתחילה את הרצף  הסוגר  של המילה,

וכי החלק  האמצעי ריק 

 

(q3,c,A,q7,ε)

קריאת c שניה ויותר בחלק האמצעי של המילה –

(q4,c,B,q4,BB)

קריאת b ראשונה בחלק האמצעי של המילה –

(q4,b,B,q5,ε)

קריאת b שניה ויותר בחלק האמצעי –

(q5,b,B,q5,ε)

קריאת אות ראשונה ברצף הסוגר, והיא a

(q5,a,A,q6,ε)

קריאת אות ראשונה ברצף הסוגר, והיא c

(q5,c,A,q7,ε)

קריאת a שניה ויותר ברצף הסוגר, כאשר עדיין לא נקראו אותיות c

(q6,a,A,q6,ε)

קריאת c ראשונה ברצף הסוגר, כאשר נקראו לפניה אותיות a,

ולפני ריקון המחסנית –

 

(q6,c,A,q8,ε)

קריאת c ראשונה ברצף הסוגר, שמביאה לריקון המחסנית,

כאשר לפניה נקראו אותיות a

 

(  (q6,c,S,q9,ε)

קריאת c שניה ויותר ברצף הסוגר, כאשר עדיין לא נקראו אותיות a

(q7,c,A,q7,ε)

קריאת a ראשונה ברצף הסוגר,

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

 

(q7,c,A,q8,ε)

קריאת a ראשונה ברצף הסוגר, שמביאה לריקון המחסנית,

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

 

(  (q7,a,S,q9,ε)

קריאת a ברצף הסוגר, כאשר לפניה נקראו לפחות a אחת ולפחות c אחת,

ועוד לא התרוקנה המחסנית –

 

(q8,a,A,q8,ε)

קריאת c ברצף הסוגר, כאשר לפניה נקראו לפחות a אחת ולפחות c אחת,

ועוד לא התרוקנה המחסנית –

 

(q8,c,A,q8,ε)

קריאת a ברצף הסוגר, שמביאה לריקון המחסנית,

כאשר לפניה נקראו לפחות a אחת ולפחות c אחת –

 

(q8,a,S,q9,ε)

קריאת c ברצף הסוגר, שמביאה לריקון המחסנית,

כאשר לפניה נקראו לפחות a אחת ולפחות c אחת –

 

(q8,c,S,q9,ε)

 

חזרה

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

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