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

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

איריס ברגורי צור

 

שאלה 1

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

 

פתרון

לאוטומט 7 מצבים:

q0 – הוא המצב ההתחלתי, הזוכר כי עדיין לא נראתה אף אות a.

q1 – זוכר כי נראתה בדיוק אות a אחת.

q2 – זוכר כי נראו בדיוק 2 אותיות a והאות האחרונה שנקראה היא a.

q3 – זוכר כי נראו בדיוק 2 אותיות a והאות האחרונה שנקראה היא b.

q4 – זוכר כי נראו לפחות 3 אותיות a ושתי האותיות האחרונות שנקראו הן aa.

q5 – זוכר כי נראו לפחות 3 אותיות a ושתי האותיות האחרונות שנקראו הן ab.

q6 – זוכר כי נראו לפחות 3 אותיות a ושתי האותיות האחרונות שנקראו הן ba.

q7 – זוכר כי נראו לפחות 3 אותיות a ושתי האותיות האחרונות שנקראו הן bb.

המצבים המקבלים הם q6 ו-q7.

 

חזרה

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

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