שאלה בשפות רגולריות -- אוטומטים

[generala]

שאלה בשפות רגולריות -- אוטומטים

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

 

[vinney]

אולי פשוט תעלה את מה שרשמת?

בשעה הזאת אוטומטים לא באים לי טבעי

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

 

[generala]

כעיקרון

זה משהו פשוט ברמת המצ"ב... אני פשוט לא יודע אם אני צודק...

אני מרגיש שאני מקיף משהו קרוב...

 

[vinney]

אני חושב שזה דורש קצת הסבר

מופיעים לך פה שני אלף-ביתים, בשאלה יש רק אחד, זה כבר לא טוב לדעתי

 

[generala]

אוי.... איזה שטות...

התבלבלתי בענק.. עכשיו אני בכלל מבולבל....

 

[דודהלי]

תבנה אוטומט א"ד לשפה הזו

נניח ש-M הוא הDFA של L. נבנה N שהוא NFA עבור Lכובע. N מתחיל במצב s ואז קורא אות אחת כלשהי ואח"כ עובר למצב ההתחלתי של M. הוא מנחש שהוא גמר לקרוא את מיו1 (הוא יכול לנחש את זה רק כשהוא במצב מקבל של M) ואז הוא קורא אות אחת ועובר למצב q שהוא מצב מקבל. ממצב q יש מעבר-אפסילון ל-s. אם המלה הריקה נמצאת ב-L, אז s ג"כ מקבל ובעצם אפשר לוותר על q ולאחד אותו עם s.

 

[generala]

אתה יכול

לרשום את מצבי האוטומט ? כי לא ממש הבנתי...

 

[שיר אהבה מתוק]

...

נניח שיש לך אוטומט סופי דטרמיניסטי עבור L. נבנה אוטומט סופי לא-דטרמיניסטי עבור L כובע. הרעיון הוא שהאוטומט החדש ינחש איזו סיגמא צריך לקרוא (מבלי לקרוא אותה ממש), יקרא את מיו מתוך הקלט, וינחש איזו קסי צריך לקרוא, וכל זאת עד לסיום קריאת כל הקלט. באוטומט החדש המצבים יתחלקו ל-3 קבוצות. בכל קבוצה יופיעו כל המצבים של האוטומט המקורי. באוטומט החדש יהיו 3 סוגים של מעברים: 1. מעברי אפסילון מהקבוצה הראשונה לשניה, כאשר יהיה מעבר בין מצב q בקבוצה הראשונה למצב r בקבוצה השניה אם"ם יש מעבר (כלשהו) בין q ל-r באוטומט המקורי. 2. מעברים "רגילים" בין הקבוצה השניה לקבוצה השלישית, שזהים למעברים של האוטומט המקורי. כלומר יהיה ניתן לעבור ממצב q בקבוצה השניה למצב r בקבוצה השלישית ע"י קריאת אות a אם"ם אפשר לעבור ממצב q למצב r ע"י קריאת a באוטומט המקורי. 3. מעברי אפסילון מהקבוצה השלישית לראשונה, כאשר יהיה מעבר בין מצב q בקבוצה השלישית למצב r בקבוצה הראשונה אם"ם יש מעבר (כלשהו) בין q ל-r באוטומט המקורי.