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

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

לאה יעקובוביץ

 

שאלה 1

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

המכילות לפחות פעם אחת את הרצף abc ומיד אחרי כל אות b מופיע הרצף cc.

 

פתרון

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

זהו אוטומט סופי דטרמיניסטי עבור השפה הראשונה

 

 

וזהו אוטומט סופי דטרמיניסטי עבור השפה השניה

 

 

ניתן לקבל אוטומט עבור השפה המבוקשת ע"י שימוש בטכניקת המכפלה כדי לבנות אוטומט לשפת החיתוך של שתי השפות:

 

 

בבנייה הדרגתית מגיעים ל-12 מצבים (במקום 16 בבנייה מלאה).

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

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

 

 

שאלה 2

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

מהצורה w=w1w2w3

כאשר w1 היא רצף של אותיות 0,    w2רצף של אותיות 1,  w3 רצף של אותיות 2 ואורך המילה זוגי.

 

פתרון

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

 

 

שאלה 3

בנה אוטומט המקבל את שפת כל המילים מעל הא"ב {0,1,2} המתחילות ברצף 01 ומסתיימות ב-1.

 

פתרון

במקרה זה חשיבה אי-דטרמיניסטית אינה מפשטת את האוטומט:

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

 

 

וזהו אוטומט אי-דטרמיניסטי המקבל את השפה

 

 

נשים לב שאם השפה היתה מוגדרת: שפת כל המילים מעל הא"ב {0,1,2} המתחילות ב-0 ומסתיימות ב-1, אז חשיבה אי-דטרמיניסטית כן היתה תורמת תרומה משמעותית למורכבות האוטומט הנבנה:

 

 

חזרה

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

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