בעיה עם אוטומט מחסנית :

[שאקל]

בעיה עם אוטומט מחסנית :

יש לי אוטומט מחסנית ונתון שרשור של שתי מלים A ו-B. האוטומט צריך לבדוק שני דברים: קודם כל ש-A ו-B שונים (לא אותה מילה בדיוק) וגם שהם באותו אורך. את האורך אין בעיה לבדוק, זה לא שונה מכל תרגיל אחר שאוטומט מחסנית מאפשר לנו לספור, רק שאני מתקשה עם הקטע של A ו-B שונים. ברור לי כי האוטומט יהיה לא דטרמיניסטי. החשיבה שלי עד כה היא כזאת: נקרא את A ועל כל תו מ-A נכניס למחסנית איזשהו סימון, נניח @. בשלב מסוים האוטומט מחליט "לנחש" כי האות שהוא כרגע קורא ב-A היא האות הזהה בין שתי המילים ולכן זה אומר שA ו-B לא שונות. את האות שהוא "מנחש" נכניס למחסנית כדי לשמור עליה. כעת אני אמשיך לקרוא את האותיות שנותרו ב-A ואכניס עוד @ על כל אחת מהן. האוטומט הגיע לסוף A , מנחש שהוא עובר לקרוא את B. כעת אני בבעיה העיקרית: כיצד אני מגיע לאות שנמצאת באותו מקום כמו האות שניחשתי שהיא הבעייתית? נניח ניחשתי שהאות ה-i במילה A היא הבעיה. כעת עלי להגיע למיקום ה-i ב-B. רק שאין לי כרגע שום אופציה כזו כי ע"י שליפות מהמחסנית לא בטוח אגיע למקום הi של B אלא לסתם איזשהו אינדקס. אני אשלוף מהמחסנית @ עד שאגיע לאות שאותה אני רוצה לבדוק עם הקלט. אבל אין שום הבטחה שאני יגיע בדיוק לאינדקס הנכון בB לצורך ההשוואה. האם הפתרון כאן מתמטי או שפספסתי משהו?

 

[גיל14]

אתה בטוח? למיטב ידיעתי,

השפה

{ ww | w is a word over {a,b} }​

היא לא חופשית-הקשר...

 

[גיל14]

אהה, השלילה שלה כן חופשית הקשר

אבל בדיוק בגלל התכונה הזו, האוטומט שמקבל את השפה הזו הוא די מאוד מסובך. לחתוך אותה בנוסף עם מילה שהיא באותו האורך לא נראה לי מסובך. נסה לחפש אוטומט מתאים בגוגל (Push-down automaton באנגלית). אתה צריך להוכיח שהשפה חופשית-הקשר, או לבנות ממש אוטומט?

 

[shirbi]

עניתי על שאלה דומה לזו בשרשור בשבוע שעבר

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

 

[שאקל]

תודה. אני חושב שמצאתי

יש רק בעיה אחת. נראה לי שאינני מבין כהלכה את הנושא של דקדוק חסר הקשר. אני שולט היטב באוטומט מחסנית אך לא בדקדוק. אולי למישהו יש לינק למקור מידע טוב שמסביר את הנושא מהיסוד?