PDA

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



exx8
28-03-2013, 15:41
היי, תרגיל שנתקלתי בו מחוץ לספר
הייתי מעוניין לדעת מהו אוטומט המחסנית של
l={x^2f*w^m*x^3f|f>=0,m>1,w=R(w)

wמילה מעל הא"ב {x y z}

אם היה מדובר במילה אחת הפתרון היה פשוט, אך היות שמדובר בזוג פולנידרומים (ומעלה, כלומר m גדול מ-1)קיים צורך להשוות את החצי הראשון של הפולינדרום לשני, ואת השני לשלישי וכך הלאה. כפועל יוצא נראה שלא ניתן לכתוב אוטומט מחסנית לשפה הזו.או שאני לא הבנתי את השאלה?
אם היה מדובר בפולינדרום אחד ומעלה אז גם כן היה פתיר, שכן פשוט הייתי חוצה את w ומשווה את החצאים שלה שכן שרשור פולינדרומי (מחרוזת המכילה חזרה של פולינדרום מאותו סוג)הוא פולינדרום בעצמו (וקל להוכיח את זה).

avishay12456
28-03-2013, 16:55
השפה לא ממש ברורה, רשמת בתנאים m>1 ואח"כ m>0 ובנוסף רשמת k>0 ואין שימוש ב-k בשפה בכלל.
תוסיף בבקשה גם את הא"ב של השפה כולה, f ו-q אותיות ב-א"ב?

exx8
28-03-2013, 17:25
תקנתי, עמך הסליחה.
f הוא חלק מהמעריך

exx8
31-03-2013, 00:07
נראה כי, שאלה זו בלתי אפשרית!

avishay12456
31-03-2013, 00:12
מצטער ששכחתי לחזור לענות חח, עד כמה שאני יודע בלתי אפשרי לזכור מילים עם אוטומט מחסנית וזה מה שאתה צריך לעשות פה.
מצד אחד צריך להשוות חצי ראשון של המילה w לחצי השני, ומצד שני לוודא שאותה מילה חוזרת על עצמה. לדעתי בלתי אפשרי לבנות אוטומט מחסנית לשפה, אתה מוזמן לנסות להוכיח זאת באמצעות המשפטים המתאימים. אמור להיות אפשרי להוכיח את זה עם למת הניפוח לשפות חסרות הקשר.
שיהיה בהצלחה ושבוע טוב!

exx8
31-03-2013, 00:22
תודה על המענה המהיר.
חשבתי על למת הניפוי, הבעיה שאני לא יכול להגיע למצב של אינסוף מצבים כפי שצריך בהוכחה, חשבתי על הטיעון שלך אבל הוא לא קביל כי הוא לא הוכח (לפי מיטב זכרוני).

avishay12456
31-03-2013, 00:28
אני הצגתי טיעון אינטואיטיבי שאמור לתת כיוון לגבי אם הדבר אפשרי או לא, לא באתי לתת הוכחה פורמלית חח.
כדי להוכיח פורמלית אתה יכול כמו שכתבתי מקודם להניח בשלילה ולהראות שלמת הניפוח לשפות חופשיות הקשר (http://he.wikipedia.org/wiki/%D7%9C%D7%9E%D7%AA_%D7%94%D7%A0%D7%99%D7%A4%D7%95% D7%97_%D7%9C%D7%A9%D7%A4%D7%95%D7%AA_%D7%97%D7%95% D7%A4%D7%A9%D7%99%D7%95%D7%AA_%D7%94%D7%A7%D7%A9%D 7%A8) לא מתקיימת.