אוטומט מחסנית זה שיקוץ

[MegaMango]

אוטומט מחסנית זה שיקוץ

או לפחות השאלה הזו- בנה אוטומט מחסנית לשפה הבאה-

{(a^nb^n)^n/n>0}​

חשבתי להוסיף למחסנית 2 Bים בהתחלה על כל a ואז להוריד B על כל b. אחרי זה, להמשיך רגיל (להוסיף A בקבלת a ולהוריד A בקבלת b תוך כדי שכל סיבוב של a^nb^n מורידים אחד מה Bים ואז בודקים אם מספר הBים הוא אפס או לא. זה לא יעבוד כי אז יהיה מילים שהן כן אמורות להיות בשפה ובכל זאת לא יתקבל בגלל שבשלב הראשון מס' הaים לא יהיה שווה למספר הbים. כן , אני יודע שזה ממש לא מובן..אבל אין לי רעיון טוב יותר איך להסביר את זה >.>

 

[MegaMango]

אני חושב שפתרתי. אשאיר את השאלה

בשביל השעשוע שלכם :]

 

[vinney]

נסיון

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

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

 

[MegaMango]

ממ...לא ממש הבנתי

או שלא הבנתי את הפיתרון, או שלא הסברתי מספיק טוב את השאלה. הכוונה הייתה לא רק a בחזקת n משורשר ל b בחזקת n , אלא שכל זה משורשר לעצמו n פעמים. הנה למשל מילה בשפה- aaabbbaaabbbaaabbb בנוסף , התבלבלתי ובכלל ביקשו את השפה המשלימה לזאת. אני אפילו לא בטוח שהשפה המקורית ח"ה P: בכל מקרה, אני ארשום עוד מעט את הפיתרון שלי. אולי אני בעצמי טעיתי...

 

[vinney]

המם...

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

זה בלי להוכיח ואחרי פחית בירה.

 

[MegaMango]

יותר מדי בירה ויני :]

אוטומט מחסנית הוא לא רגולי, הוא מקבל גם שפות ח"ה. ח"ה לא סגורות למשלים... אגב, כשמדובר באוטומט מחסנית, אי דטרמיניזם מוסיף עוד כוח לאוטומט. במקרה הזה לא בטוח שאפשר להפוך אותו לאוטומט כן דטרמיניסטי. בכל מקרה, אין בעיה עם חוסר דטר'. ו...כנראה שלא הבנת כי אני לא מחפש (ab) בחזקת n אלא השפה המשלימה למה שגיל14 רשם.

 

[vinney]

נו טוב, אני אחזור לי לבירה ../images/Emo13.gif

 

[MegaMango]

אופס. התכוונתי לשפה המשלימה.

 

[גיל14]

לא הבנתי.

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

 

[MegaMango]

המשלימה למה שרשמת.

 

[גיל14]

עדיין צריך 2.

 

[MegaMango]

2? 2 מה?

אם התכוונת ל2 מחסניות אז לא...כי התרגיל לא היה הוכח\הפרך אלא "כתוב אוטומט מחסנית שמקבל את השפה המשלימה לזו שרשמתי" לא למדנו אוטומט עם 2 מחסניות. אני מניח שהמרצה היה פיכח כשרשם את התרגיל .. בסך הכל כבר יש לי פיתרון , אין לי כח לרשום אותו בפירוט.. אנחנו מתחילים בקליטת a ים והוספת A למחסנית עבור כל a. אחרי שקראנו b, מתחילים להוריד A ים מהמחסנית. אם הגענו לסוף המחסנית ועדיין קיבלנו bים, אז מקבלים את המילה. אם אנחנו לא רוקנו את כל ה Aים מהמחסנית וקיבלנו a , גם נקבל את המילה. אם קיבלנו a בדיוק כשנגמרה המחסנית, אז נוסיף למחסנית DD. עכשיו, נתחיל מהתחלה להוסיף Aים על a ולהוריד Aים על B. בנוסף, אחרי כל פעם שאנחנו מסיימים את המחסנית ומוסיפים DD, מדי פעם, באופן לא דטרמיניסטי נקבל את הרצף a^nb^n הבא תוך כדי הורדת ממספר ה Dים. מספר הDים צריך להיות 2n (מתי שקופצים לאופציה הזו מוסיפים 2 Dים נוספים) וגם מספר האותיות ב a^nb^n צריך להיות 2n. המילה לא תתקבל אם מספר הDים זהה למספר האותיות ברצף (שהנחנו שהוא האחרון). בכל מקרה, יווצר מצב שכל המילים שהן לא מהצורה (a^nb^n)^n יתקבלו באחד מהמצבים (האל דטר') ואילו המילים שהן כן (a^nb^n)^n לא יכולות להתקבל אף פעם(האוטומט מקבל מילים רק אחרי הפנייה הלא דטר' שמניחה שזה הסוף ואם בסוף קיבלנו שזה a^nb^n זה לא יתקבל).