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

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

דורון זוהר

 

שאלה 1

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

שמתחילות ברצף cc, אח"כ מכילות לפחות פעם אחת את הרצף ab או aca ומסתיימות בחזרה מספר זוגי של פעמים על הרצף bc.

 

פתרון

נשים לב כי התנאי האחרון למעשה מתקיים בכל מקרה משום ש-0 אף הוא מספר זוגי ולכן כל מילה מסתיימת בחזרה מספר זוגי של פעמים על הרצף bc. לכן השפה הנדונה היא בעצם שפת השרשור של שפת כל המילים שמתחילות ברצף cc ושפת כל המילים שמכילות לפחות פעם אחת את הרצף ab או את הרצף aca.

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

 

 

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

 

 

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

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

 

 

ניתן לקבלו מצירוף ישיר או ע"י שימוש בבניית אוטומט שרשור וצירוף המצב המקבל של האוטומט הראשון והמצב ההתחלתי של האוטומט השני.

 

אם היינו דורשים כי המילה תסתיים בחזרה מספר זוגי וגדול מ-0 של פעמים על הרצף bc, זה אוטומט מתאים:

 

 

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

 

חזרה

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

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