נושא: מודלים חישוביים-אני חייב עזרה...

נשלח בתאריך: 26 April 2009 בשעה 19:45 | IP רשוּם

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

אני ממש אשמח אם תסבירו לי.

הנה דוגמא שראיתי, אבל לא הבנתי הרבה דברים ולא את הרעיון הכללי:

(השאלות באפור הן שלי..)

השפה  { aⁿbⁿ | n >= 0 } = L  אינה רגולרית

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

נסתכל על קבוצת המילים { aⁿ | n >= 0 }=W.

נניח בשלילה, שקיימות בקבוצה זו שתי מילים  a^I (1w)  ו-  a^j  (2w),

שעליהן מגיע האוטומט לאותו מצב q.  נניח כי  j > i .  

w1 w2?.??

נסתכל על המלה  a^Ib^I  (w  ●  1w ) :  מלה זו שייכת לשפה

כי מספר האותיות  a  שבה שווה למספר האותיות  b .

1.      למה  המלה  ==a^Ib^I  (w  ●  1w )

על מלה זו מגיע האוטומט A למצב מקבל.  כלומר, מהמצב  q  האוטומט מגיע

למצב מקבל על המלה  b^I ( w ).

אבל, מכאן נובע, שאוטומט זה מקבל גם את המלה   a^jbⁱ  (w  ●  2w ) ,

2. ממה נובע שהאוטומט  זה מקבל גם את המלה   a^jbⁱ  ??

שאינה שייכת לשפה כי מספר האותיות  a  שבה אינו שווה למספר האותיות  b  ,

בסתירה להיותו אוטומט, המקבל את השפה L.  מכאן נובע, שהנחת השלילה

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

המסקנה המתבקשת היא, שגם הנחת השלילה הראשונה הייתה שגויה, כלומר, לא קיים אוטומט סופי, המקבל את השפה L , ובמילים אחרות:  L  אינה רגולרית.

3. וגם באופן כללי לא ברור לי למה ואיך הגענו לסתירה...

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

נשלח בתאריך: 02 May 2009 בשעה 20:57 | IP רשוּם

אם השאלה שלך היא מה שכתבת: "לפי מה אתה בוחר את המילים" - אז לפי שפת הקלט שמצויינת בהגדרת האוטומט.