דף עבודה בנושא בניית אוטומט סופי דטרמיניסטי עם פתרונות מלאים

1. בנה אוטומט סופי דטרמיניסטי לא מלא A מעל {a,b,c} שמתחיל במצב התחלה q0 ומקבל את השפה הבאה A לדוגמה: bbca, bbcabaca, bcbabbbba: bbca, bbcabaca, bcbabbbba
2. בנה אוטומט סופי דטרמיניסטי מלא A מעל

L = {a,b,c | x%3=2):

האם כתבו באוטומט A? יש הבדל בין אוטומט סופי דטרמיניסטי מלא ללא מלא?

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

3. בנו אוטומט סופי דטרמיניסטי המקבל את שפת כל המילים שמתחילות ב-11 ומסיימות ב- 10
4. בנו אס"ד המקבל את שפת כל המילים שמתחילות ב- 01 ומכילות את הרצף 11
5. בנו אס"ד המקבלת את שפת כל המילים המסתיימות ברצף 1011

פתרון:

פתרון מלא לשאלה 3

התחנה q0 היא תחנה התחלתית

התחנה q1 זוכרת כי המילה מתחילה ב-1

התחנה q2 זוכרת כי המילה מתחילה ברצף 11 ומסתיימת ב-1.

התחנה q3 זוכר כי המילה התחילה ברצף 11 והסתיימה ברצף 10.

התחנה q4 זוכרת כי המילה התחילה ברצף 11 ומסתיימת ב-0 או 2. ובפרט לא מסתיימת ב-10.

התחנה q5 זוכרת כי המילה לא התחילה ברצף 11, או שהחילה ב-0 או 2 וכבר אי אפשר לתקן זאת (מצב מלכודת).

פתרון מלא לשאלה 4

התחנה q0 היא מצב התחלתי

התחנה q1 זוכרת כי ישנה התחלה של 0

התחנה q2 זוכרת כי היית התחלה של 01 (כלומר תנאי ראשון בוצע).
התחנות q3,q4,q5 גם הן זוכרות שהתנאי ההתחלתי (התחלה עם 01 בוצעה).

התחנה q3 זוכרת בנוסף כי גם התנאי השני התקיים, המילה מכילה רצף 11.

התחנה q4 זוכרת כי אין התחלה של הרצף 11.

התחנה q5 זוכרת כי יש התחלה של הרצף 11, והוא 1.

התחנה q6 היא מצב מלכודת שבו לא התחלנו ברצף 01 ולכן המילה לא תתקבל לא משנה מה.

פתרון מלא שאלה 5

התחנה q0 היא תחנה התחלתית

התחנה q1 זוכרת כי הסיומת מסתיימת ב-1 ובפרט לא ב- 101 או 1011

התחנה q2 זוכרת כי הסיומת היא רצף של 10

התחנה q3 זוכרת כי הסיומת היא רצף של 101

התחנה q4 זוכרת כי הסיומת היא רצף של 1011

התחנה q5 זוכרת כי אין סיומת של 1, 10, 101 או 1011.