28-02-2011, 10:35
|
|
|
חבר מתאריך: 11.02.04
הודעות: 16,543
|
|
אין איזו שיטה אונברסלית..
הכל עניין של תרגול.
בכדי להשתמש בלמת הניפוח לא צריך לדעת את הN המנימלי! צריך להניח בשלילה שהוא קיים! ואז להגיע לסתירה.
הנה יש פה כמה תרגלים+פתרונות
http://www.cs.bgu.ac.il/~auto111/As...ts/Assignment_3
הבהרה:
בלמת הניפוח משתמשים(כמו שאמר הבחור מעלי) רק כדי לסתור רגולריות של שפה, שכן המשפט הוא לא אם"ם, כלומר יש שפות שעומדות בתנאי למת הניפוח, אבל אינם רגולריות.
בניגוד לכך כל שפה רגולרית בהכרח מקיימת את למת הניפוח.
אם אתה משום מה מתעקש ממש למצוא את הN המובטח מלמת הניפוח, הדרך לעשות זאת הוא למצוא את מחלקות השקלות של השפה, מספר מחלקות השקלות שווה לN הנ"ל=למספר מצבים באוטומט דטרמניסטי מינימלי המכיר שפה זו.
ציטוט:
כמו שעבור השפה *00001 הקבוע המינימלי הוא 5 , מכיוון שמאחר "יש חובה" ל 4 אפסים ראשונים ואסור ש Y יהיה שווה לאפסילון , Y חייב להיות ל - '1' אחד לפחות.
לכן לי הפירוק :
x = 0000
y = 1
z = כל שאר ה-1 שיכולים להגיע (במידה והם קיימים )
דוגמא נוספת השפה 0*1*0 - כאן קבוע הניפוח הוא 2 , מכיוון שיש חובה על ה0 הימני ביותר להופיע ונקח אותו בתור ה Z , בתור ה -Y נקח את אחד המופעים של *0 או *1 ו את X אפשר לקחת כ אפסילון.
|
בשני הדוגמאות שנתת, יש טעות בידך!(הN שנסית לחשב לא נכון בעליל)! איך אני רואה זאת מיידית? N=למספר מצבים באוטומט דטרמניסטי מינימלי המכיר את השפה, נסה לחשוב על אוטומט דטרמניסטי בעל 5 מצבים המכיר בשפה א, ובאוטומט 2 מצבים המכיר את שפה ב..
אני חושב שיש לך בעיות הבנה בכל הקשור ללמת הניפוח, קרא את ההסבר שלי אודות הלמה, קראה סיכומים באינטרנט.
http://he.wikipedia.org/wiki/%D7%9C...%99%D7%95%D7%AA
ואז נסה לתרגל.
נערך לאחרונה ע"י The_Equivocator בתאריך 28-02-2011 בשעה 11:04.
|