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

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

ריקה רם

 

שאלה 1

בנה אוטומט סופי עבור השפה הבאה מעל הא"ב {a,b,c}:

     L = L1∙L2∙L3∙L4

כאשר:  

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

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

L3  היא שפת כל המילים מעל הא"ב {a,b,c} המורכבת מאותיות a או אותיות b בלבד, ואורכן זוגי.

L4  היא שפת כל המילים מעל הא"ב {a,b,c} המורכבת מאותיות c בלבד ואורכן זוגי.

 

פתרון

הנה אוטומט עבור  L1:

 

הנה אוטומט עבור  L2:

 

הנה אוטומט עבור  L3:

 

הנה אוטומט עבור  L4:

 

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

שלב ראשון: 

 

ואז ניתן לוותר על p0 ועל המעברים היוצאים ממנו:

 

 

שלב שני:

 

שלב שלישי:

הערה:

אוטומט עבור  L2 ניתן לקבל גם ע"י פירוק נוסף:

L5 – שפת כל המילים שמתחילות ב-a.

L6 – שפת כל המילים שמתחילות ב-b.

L7 – שפת כל המילים המכילות aa.

L8 – שפת כל המילים המכילות bb.

 או  

 

אלא שיש להיזהר בבניית המשלים באוטומטים לא דטרמיניסטיים כפי שכתוב בעמ' 119 במדריך למורה.

 

שאלה 2

תהי L שפת כל המילים מעל הא"ב {a,b} המקיימות לפחות אחד משני התנאים הבאים:

1. בכל רישא של המילה ההפרש בין מספר האותיות a למספר האותיות b אינו עולה בערכו המוחלט על 1.

2. אין במילה שתי אותיות שונות זו מזו.

בנה אוטומט סופי המקבל את L.

 

פתרון

נבנה אוטומט המתאים לתנאי 1:

q0 – שוויון של מספר האותיות a שנקראו עד כה ומספר האותיות b שנקראו עד כה.

q1 – מספר האותיות a שנקראו עד כה עולה ב-1 על מספר האותיות b שנקראו עד כה.

q2 – מספר האותיות b שנקראו עד כה עולה ב-1 על מספר האותיות a שנקראו עד כה.

 

 

את תנאי 2 נפרק לשני תת-תנאים:

2.1 המילה אינה מכילה אותיות b.

2.2 המילה אינה מכילה אותיות a.

אוטומט המתאים לתנאי 2.1 הוא    

 

אוטומט המתאים לתנאי 2.2 הוא

 

אם אנו מסמנים ב-L1 את השפה המוגדרת ע"י תנאי 1,

ב-L2  את השפה המוגדרת ע"י תנאי 2.1

וב-L3 את השפה המוגדרת ע"י תנאי 2.2 אז (L=L1È(L2ÈL3.

לכן, כדי לקבל אוטומט עבור L נשתמש בבניית אוטומט איחוד. ראשית נבנה אוטומט המקבל את L2ÈL3:

 

 

ועתה נבנה אוטומט המקבל את (L1È(L2ÈL3:

 

r0 הופך להיות מיותר והאוטומט הוא בעצם:

 

חזרה

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

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