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

בניית אוטומט סופי

אתי מנשה

 

שאלה 1

בנה אוטומט סופי המקבל את שפת כל המילים מעל הא"ב {0,1,2}

כך שניתן לחלקן לשני חלקים:

בחלק הראשון מספר האותיות 0 ו-1 גם יחד אינו עולה על 5 ומספר האותיות 0 גדול ממספר האותיות 1

והחלק השני אינו מכיל את הרצף 012.

 

פתרון

נבנה ראשית אוטומט עבור כל אחד מהחלקים. אוטומט עבור החלק הראשון דומה לאוטומט עבור השפה L4 משאלה 3 של רחלי צרניחוב:

 

 

כאשר qij מציין שנקראו i אותיות 1 ו-j אותיות 0.

אוטומט עבור החלק השני הוא למשל:

 

 

ניתן גם לקבלו מאוטומט עבור השפה המשלימה – שפת כל המילים שמכילות את הרצף 012 ושימוש בבניית אוטומט משלים. בכל מקרה, לא ניתן להיעזר במנגנון האי-דטרמיניסטי לצורך בניית האוטומט הזה (אמנם ניתן להיעזר בו כדי לבנות אוטומט לשפה המשלימה, אבל אז לא ניתן להשתמש בבניית אוטומט משלים שאינה עובדת עבור אוטומט לא דטרמיניסטי).

אוטומט עבור שפת השרשור הוא האוטומט הבא:

 

 

שאלה 2

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

* החלק הראשון מורכב משני חלקים – הראשון מבין אלו אינו מכיל את הרצף ab ובשני מביניהם מספר האותיות a אי-זוגי.

* החלק השני מורכב משני חלקים – בראשון מבין אלו מספר האותיות a אי-זוגי והשני מביניהם אינו מכיל את הרצף ba.

 

פתרון

ראשית  נתבונן בשתי שפות הבסיס הבאות מעל הא"ב {a,b}.

L1: שפת כל המילים שאינן מכילות את הרצף ab.

L2: שפת כל המילים שמכילות מספר אי-זוגי של אותיות a.

 

A1 הוא אוטומט סופי שמקבל את L1 :   

 

 

A2 הוא אוטומט סופי שמקבל את L2 :   

 

 

כעת נבנה אוטומט סופי שמקבל את L1∙L2:

 

 

כעת נבנה אוטומט סופי שמקבל את (L1∙L2)R :

 

 

(לא השתמשנו בבנייה המלאה משום שבאוטומט המקורי היה רק מצב מקבל אחד ולכן באוטומט ההיפוך מלכתחילה יש רק מצב התחלתי אחד).

עתה יש לשרשר את שני האוטומטים:

 

 

שאלה 3

בנה אוטומט סופי המקבל את שפת כל המילים מעל הא"ב {a,b}

המכילות לפחות את אחד מארבעת הרצפים: aa, bb, aabb, bbaa.

 

פתרון

נשים לב כי אם מילה מכילה את הרצף aabb או את הרצף bbaa הרי היא מכילה בהכרח את הרצף aa ואת הרצף bb, ומאחר שמספיק כי המילה תכיל את הרצף aa או את הרצף bb כדי שתהיה שייכת לשפה אין צורך לבדוק את שני הרצפים האחרונים.

לכן האוטומט הדרוש פשוט מאוד (בחשיבה לא-דטרמיניסטית):

 

 

חזרה

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

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