מבקש עזרה במודלים חישוביים

[miaoo673]

עבור שפה כללית L, נגדיר את הפעולה:

{ Inv(L) = { XYZ | X(Y^R)Z is a word in L

כאשר X,Y,Z הן מחרוזות מעל הא"ב, ו-Y^R היא המחרוזת Y ברוורס.

הוכח/הפרך:

* השפות הרגולריות סגורות תחת הפעולה Inv.

* השפות חסרות ההקשר סגורות תחת הפעולה Inv.

לגבי הסעיף הראשון,

ניסיתי להוכיח את הטענה באמצעות בניית NFA שמורכב משרשור של שלושה DFA-ים:

D1 מזהה את כל התחיליות בL, משמש לזיהוי X.

D2 מזהה את כל תתי המחרוזות בL^R, משמש לזיהוי Y^R.

D3 מזהה את כל הסיומות בL, משמש לזיהוי Z.

הבעיה מתעוררת במעברים בין הDFA-ים.

בחלק מהשפות הרגולריות, האורך של Y^R לא חסום. בנוסף, לכל Y^R מתאים שרשור עם X-ים וZ-ים מאוד מסוימים.

ככה שלפחות על הנייר, הNFA צריך להבדיל בין כמות לא חסומה של מחרוזות, ולכן הוא כבר לא סופי.

אז כנראה קיימת איזשהי דוגמא נגדית - שפה רגולרית L כך ש(Inv(L לא רגולרית.

השאלה היא מהי L?

(וגם אשמח לעזרה בסעיף השני)

[שניצל]

אם L היא רגולרית אז גם (Inv(L היא רגולרית. אפשר להוכיח את זה באמצעות שרשורים ואיחודים של שפות רגולריות.

נניח ש-A הוא האוטומט המקבל את L. לכל שני מצבים q,r ב-A נגדיר שלוש שפות חדשות:

שפה ראשונה: (L1(q היא שפת כל המילים שהפעלת A עליהן מסתיימת במצב q.

שפה שנייה: (L2(q,r היא שפת כל המילים שהפעלת A עליהן החל ממצב q מסתיימת במצב r. השפה L2(q,r)^R היא היפוך השפה הזו (כלומר מילים שהפעלת A עליהן בסדר הפוך החל ממצב r מסתיימת במצב q).

שפה שלישית: (L3(r היא שפת כל המילים שהפעלת A עליהן החל ממצב r מגיעה למצב מקבל של A.

קל לראות ש-L היא למעשה איחוד כל השפות מהצורה (L1(q)*L2(q,r)*L3(r (לכל שני מצבים q,r), ואז למעשה (Inv(L היא איחוד כל השפות מהצורה (L1(q)*L2(q,r)^R*L3(r.

אפשר גם לעשות את אותו דבר עם אוטומטים, פשוט צריך עותקים של האוטומט עם שינויים קלים.

[miaoo673]

יפה. תודה רבה.

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

(רק שהפעם משתמשים באוטומט מחסנית)

[שניצל]

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

[miaoo673]

מישהו יכול לחשוב על איזושהי דוגמא נגדית?

[עוד אחד]

ניסית לעשות שלילה של למת הניפוח ?

זה פותר את רוב השאלות הללו.

[miaoo673]

זה הכיוון הכללי. ואז אני מקבל ש(Inv(L היא איחוד של הרבה שפות, חלק מהן אכן לא חסרות הקשר.

הבעיה היא, לך תדע אם ניפוח מילה בשפה אחת לא יעביר אותך לשפה אחרת באותו איחוד.