PDA

צפה בגרסה המלאה : תרגיל באוטומט מחסנית



J123
26-12-2015, 13:00
שלום,
אשמח אם מישהו יוכל לעזור לי לבנות את אוטומט המחסנית הבא:
\left \{ a^{n}b^{k}c^{m}|n\geq k>m\geq 0 \right \}



אני לא מצליח לחשוב על דרך לוודא שכמות ה-a תהיה גדולה/שווה מכמות ה-b ושזו תהיה גדולה מכמות ה-c...
אשמח לעזרה! :)

shlomi4446
26-12-2015, 17:43
תכניס A למחסנית עד שתראה b. על כל b תוציא A. לאחר מכן כשתראה c תמשיך להוציא A. אם בסוף בתוך המחסנית נשאר לפחות A אחד אז אתה במצב מקבל. אחרת, לא

J123
26-12-2015, 18:04
תכניס A למחסנית עד שתראה b. על כל b תוציא A. לאחר מכן כשתראה c תמשיך להוציא A. אם בסוף בתוך המחסנית נשאר לפחות A אחד אז אתה במצב מקבל. אחרת, לא

תודה על התשובה, אך עבור הקלט aaaabbbcc מה שכתבת לא תקף - למחסנית יידחפו 4 תווים (עבור כל אחד מ-4 ה-a), ואם על כך b שולפים a ואח"כ גם על כל c שולפים a, המחסנית תיתקע כי יש לשלוף ממנה 5 פעמים, ולכן המילה לא תצא שייכת לשפה למרות שהיא כן אמורה להיות...

chenkop
01-03-2016, 02:12
תודה על התשובה, אך עבור הקלט aaaabbbcc מה שכתבת לא תקף - למחסנית יידחפו 4 תווים (עבור כל אחד מ-4 ה-a), ואם על כך b שולפים a ואח"כ גם על כל c שולפים a, המחסנית תיתקע כי יש לשלוף ממנה 5 פעמים, ולכן המילה לא תצא שייכת לשפה למרות שהיא כן אמורה להיות...

השפה לא חופשית הקשר, לא ניתן לבנות לה אוטומט מחסנית.