PDA

צפה בגרסה המלאה : עזרה || אוטומט לא דטרמינסטי



blablabla1
02-12-2013, 12:05
א. תאר אוטומט דטרמינסטי המקבל את שפת כל המילים מעל הא"ב {a,b} שבהן האות שלפני האחרונה היא a.
ב. תאר אוטומט לא דטרמינסטי המקבל את השפה שתוארה בסעיף א.

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

- - - - - - הודעה נוספת - - - - - -

לא משנה אני חושבת שהבנתי מה לעשות

מיכאל
02-12-2013, 20:27
אז תעלי פתרון לחברים

imper
24-04-2014, 02:28
כל הרעיון באוטומט סופי לא דטרמיניסטי (או אסל"ד) הוא שצריך לוודא כי עבור קלט תקין בשפה יהיה קיים לפחות מסלול אחד אשר יביא אותו למצב "מקבל" ועבור קלט שגוי לא יהיה מצב כזה כלל.
לגבי מצב של "תקיעה" אפשרית במהלך הדרך, צריך לזכור שזה בסדר גמור באסל"ד. בתרחיש מסוים בו את מגיעה למצב "היתקעות", זה נחשב כלא מתקבל.
30614

chenkop
18-07-2015, 12:59
א. תאר אוטומט דטרמינסטי המקבל את שפת כל המילים מעל הא"ב {a,b} שבהן האות שלפני האחרונה היא a.
ב. תאר אוטומט לא דטרמינסטי המקבל את השפה שתוארה בסעיף א.

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

- - - - - - הודעה נוספת - - - - - -

לא משנה אני חושבת שהבנתי מה לעשות

הפתרון שלך לסעיף א' לא נכון.... קודם כל השפה מעל הא"ב {a,b} כך שלא אמורים להיות מעברים עם האות c, חוץ מזה, המילה aa אמורה
להתקבל ואצלך היא לא מתקבלת... הפתרון הנכון ל-א' הוא:
36589

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