שאלה באוטומטים ושפות פורמליות
- פותח הנושא אורןפרי1
- פורסם בתאריך
זה פשוט למת הניפוח
נניח p קבוע הניפוח של השפה L, נבחר במילה zzz 1^p0^(p+1) zz ברור שהמילה בשפה, כעת נניח קיימת חלוקה xyz של המילה כך ש zz |xy|<p zz כלומר בהכרח y=1^i לאיזשהו i וברור כי i>0 כעת עבור n מספיק גדול, נקבל מילה מהצורה zzz 1^(p-i)1^(ni)0^(p+1) zz ועבור i מספיק גדול, המילה לא בשפה. לגבי הביטוי הרגולרי, שים לב שבגלל שמספר האפסים גדול שווה ממספר האחדות, ובשפה 1* יש רק מספרים מהצורה 1 (ייתכן גם אפסילון, המילה הריקה), אז בעצם מדובר על כך שמדובר בשפה L ללא המילה הריקה, כלומר תחייב לפחות מקרה אחד. כעת לא נראה לי צריכה להיות בעיה לרשום את הביטוי במפורש...
נניח p קבוע הניפוח של השפה L, נבחר במילה zzz 1^p0^(p+1) zz ברור שהמילה בשפה, כעת נניח קיימת חלוקה xyz של המילה כך ש zz |xy|<p zz כלומר בהכרח y=1^i לאיזשהו i וברור כי i>0 כעת עבור n מספיק גדול, נקבל מילה מהצורה zzz 1^(p-i)1^(ni)0^(p+1) zz ועבור i מספיק גדול, המילה לא בשפה. לגבי הביטוי הרגולרי, שים לב שבגלל שמספר האפסים גדול שווה ממספר האחדות, ובשפה 1* יש רק מספרים מהצורה 1 (ייתכן גם אפסילון, המילה הריקה), אז בעצם מדובר על כך שמדובר בשפה L ללא המילה הריקה, כלומר תחייב לפחות מקרה אחד. כעת לא נראה לי צריכה להיות בעיה לרשום את הביטוי במפורש...
לא
השפה המסומנת בביטוי הרגולרי 1* היא השפה zzz {w|w=1^i, i>=0} zz הפשה הראשונית לא נותנת לנו אף הגבלה על המבנה הפנימי של המילה (למרות למשל שהשפה zzz {w|w=0^n1^n,n>=0} zz ודומותיה גם לא רגולריות (ככל יש כאן צורך במונה כלשהו שלא ידוע מראש, הפאטרן הוא מאורך דינאמי, ואז פשוט מהסופיות של אוטומט סופי וחוסר הזיכרון שלו, אתה נכשל)). כלומר אפשר למשל לקחת את 01, הוא מילה בשפה, והוא גם לא מהצורה 1* ולכן גם נמצא בשפה של ההפרש. נ.ב. אם קשה לך לראות את זה, ולא רוצה להתחיל לצייר כאן דיאגרמות ון, אפשר לחשוב על זה בצורה הבאה: zzz A\B=a intersect (B^c) zz כאשר B^c הינה המשלימה של B מעל האלף-בית {0,1}.
השפה המסומנת בביטוי הרגולרי 1* היא השפה zzz {w|w=1^i, i>=0} zz הפשה הראשונית לא נותנת לנו אף הגבלה על המבנה הפנימי של המילה (למרות למשל שהשפה zzz {w|w=0^n1^n,n>=0} zz ודומותיה גם לא רגולריות (ככל יש כאן צורך במונה כלשהו שלא ידוע מראש, הפאטרן הוא מאורך דינאמי, ואז פשוט מהסופיות של אוטומט סופי וחוסר הזיכרון שלו, אתה נכשל)). כלומר אפשר למשל לקחת את 01, הוא מילה בשפה, והוא גם לא מהצורה 1* ולכן גם נמצא בשפה של ההפרש. נ.ב. אם קשה לך לראות את זה, ולא רוצה להתחיל לצייר כאן דיאגרמות ון, אפשר לחשוב על זה בצורה הבאה: zzz A\B=a intersect (B^c) zz כאשר B^c הינה המשלימה של B מעל האלף-בית {0,1}.
אלוהים ישמור, מה זה המילים האלה?
נכון שאפשר להגדיר כל מיני הגדרות אלגבריות (ואף טופולוגיות!) על שפות, אבל אין טעם להסתך יתר על המידה, לפחות בקורס לתואר ראשון (אם אתה לומד בוייצמן אצל גולדרייך, זה כבר סיפור אחר). בכל אופן, נניח בשלילה שהשפה רגולרית, המשלימה של השפה 1* היא רגולרית (כל דבר שיתחיל ב0 תקבל, אחרת תדחה), תחתוך אותה יחד עם השפה הנתונה, תקבל מתכונת הסגור של השפות הרגולריות שפה רגולרית. כעת נשאר לך להוכיח שהשפה zz L'={w|w=0^k(111)^(2^m), k,m>=0 } zz איננה רגולרית. כעת ברור שהחלק של ה 0 בחזקת k כאשר k>=0 לא מעניין אותנו (קל לבנות משהו שיקבל את זה, פשוט תעבור למצב שכל הזמן יקבל כל עוד הוא מקבל אפסים), אנחנו נתקעים בבחור השני. נניח p קבוע הניפוח, נסתכל במילה zzz (111)^(2^p) zz נניח שיש חלוקה xyz כאשר y לא ריק ונסתכל ב xyz וב xy^2z zz |xyz|=3*2^p זוהי הצורה של כל מילה המתקבלת בשפה! (ע"י בחירת מעריך שונה כמובן)! ולכן zz |xy^2z|<=3*2^p+p zz כעת אפשר להראות שלכל x>=1 לצורך העניין (אפשר למצוא מינימום מדוייק יותר) מתקיים ש zz 2^x>x zz כלומר zz |xy^2z|<=3*2^p+p<3*2^p+2^p<=3*2^p+3*2^p=3^2^(p+1) zz כעת אורך האיבר העוקב בסדרה (כפי שהראנו) הוא zz 3*2^(p+1) zz, אך האיבר שקיבלנו קטן ממש! מאיבר זה, ולכן לא בשפה, בסתירה לרגולריות. זאת הוכחה טיפה מסובכת, אבל דומה מאוד לזאת של משהו בחזקת n בריבוע וכאלה, ייתכן שההוכחה שלך פשוטה יותר, למרות שנראה לי שאו זה, או מחלקות mn אלה הדרכים הנכונות...
נכון שאפשר להגדיר כל מיני הגדרות אלגבריות (ואף טופולוגיות!) על שפות, אבל אין טעם להסתך יתר על המידה, לפחות בקורס לתואר ראשון (אם אתה לומד בוייצמן אצל גולדרייך, זה כבר סיפור אחר). בכל אופן, נניח בשלילה שהשפה רגולרית, המשלימה של השפה 1* היא רגולרית (כל דבר שיתחיל ב0 תקבל, אחרת תדחה), תחתוך אותה יחד עם השפה הנתונה, תקבל מתכונת הסגור של השפות הרגולריות שפה רגולרית. כעת נשאר לך להוכיח שהשפה zz L'={w|w=0^k(111)^(2^m), k,m>=0 } zz איננה רגולרית. כעת ברור שהחלק של ה 0 בחזקת k כאשר k>=0 לא מעניין אותנו (קל לבנות משהו שיקבל את זה, פשוט תעבור למצב שכל הזמן יקבל כל עוד הוא מקבל אפסים), אנחנו נתקעים בבחור השני. נניח p קבוע הניפוח, נסתכל במילה zzz (111)^(2^p) zz נניח שיש חלוקה xyz כאשר y לא ריק ונסתכל ב xyz וב xy^2z zz |xyz|=3*2^p זוהי הצורה של כל מילה המתקבלת בשפה! (ע"י בחירת מעריך שונה כמובן)! ולכן zz |xy^2z|<=3*2^p+p zz כעת אפשר להראות שלכל x>=1 לצורך העניין (אפשר למצוא מינימום מדוייק יותר) מתקיים ש zz 2^x>x zz כלומר zz |xy^2z|<=3*2^p+p<3*2^p+2^p<=3*2^p+3*2^p=3^2^(p+1) zz כעת אורך האיבר העוקב בסדרה (כפי שהראנו) הוא zz 3*2^(p+1) zz, אך האיבר שקיבלנו קטן ממש! מאיבר זה, ולכן לא בשפה, בסתירה לרגולריות. זאת הוכחה טיפה מסובכת, אבל דומה מאוד לזאת של משהו בחזקת n בריבוע וכאלה, ייתכן שההוכחה שלך פשוטה יותר, למרות שנראה לי שאו זה, או מחלקות mn אלה הדרכים הנכונות...
Copyright©1996-2021,Tapuz Media Ltd. Forum software by XenForo® © 2010-2020 XenForo Ltd.