מאגר שאלות ותשובות להוראת מודלים חישוביים:

הוכחות אי רגולריות

ויקטוריה צורי

 

שאלה 1

תהי L שפת כל המילים מעל הא"ב {a,b,c,d,e} אשר הן מהצורה exeye, כאשר x היא מילה המורכבת מהתווים a ו- b בלבד ו- y היא מילה המורכבת מהתווים c ו- d בלבד, ומתקיים שמספר המופעים של האות a ב- x שווה למספר המופעים של האות  d ב- y. הוכח כי L אינה רגולרית.

פתרון

למעשה, הפתרון של שאלה זו דומה מאוד לפתרון תרגיל 3.13 מהספר לתלמיד ולכן השאלה מתאימה לעבודת כיתה או לשיעורי בית, אם אכן התלמידים כבר ראו פתרון של תרגיל 3.13 (וגם אם לא, הפתרון אינו מאוד שונה מההוכחה הסטנדרטית עבור n ³ 0} ({anbnï.

נניח בשלילה ש- L רגולרית, ולכן קיים אוטומט סופי A שמקבל אותה. נתבונן בקבוצה האינסופית הבאה W={eanïn ³ 0}. נניח בשלילה שקיימות בקבוצה זו שתי מילים eaj, eai כך ש- i≠j שהאוטומט מגיע עליהן לאותו מצב q.

נתבונן במילה eaiedie. המילה בשפה ולכן הסיפא edie מובילה את האוטומט מהמצב q למצב מקבל. אבל מכאן נובע שהאוטומט יקבל גם את המילה eajedie שאינה בשפה, בסתירה להיותו אוטומט שמקבל את L. לכן בהכרח האוטומט מגיע על כל מילה ב- W למצב שונה, ולכן נובע שיש לו אינסוף מצבים, בסתירה להיותו אוטומט סופי. לכן, בהכרח L אינה רגולרית.

נשים לב שכלל לא השתמשנו באותיות b ו- c בהוכחה!

 

שאלה 2

תהי L שפת כל המילים מעל הא"ב {a,b,c} המקיימות את התנאי הבא:

מכילות את הרצף ccc, אורכן זוגי והיחס בין מספר מופעי האות a ומספר מופעי האות b במילה הוא לפחות 2.

האם L רגולרית? הוכח את תשובתך.

פתרון

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

נניח בשלילה ש- L רגולרית ולכן קיים אוטומט סופי A שמקבל אותה. נתבונן בקבוצה האינסופית הבאה W={ccca4nïn ³ 0}. נניח בשלילה שקיימות בקבוצה זו שתי מילים ccca4i ו- ccca4j כך ש- i>j והאוטומט מגיע על שתיהן לאותו מצב q.

נתבונן במילה ccca4icb2i. המילה בשפה – היא בוודאי מכילה את הרצף ccc, אורכה זוגי (6i+4=3+4i+1+2i) ומספר מופעי a בה (4i) הוא פי 2 ממספר מופעי b בה (2i). לכן האוטומט מגיע מהמצב q עם קריאת הסיפא cb2i למצב מקבל. אבל, מכאן נובע שהאוטומט מקבל גם את המילה  ccca4jcb2i  והיא אינה בשפה. אמנם, היא מכילה את הרצף ccc, ואורכה זוגי (4+4j+2i=3+4j +1+2i), אבל, j<i ולכן 4j<2·2i (כלומר, מספר מופעי האות a קטן מפעמיים מספר מופעי האות b). לכן בהכרח האוטומט A מגיע על כל מילה ב- W למצב שונה, ומכאן נובע שיש לו אינסוף מצבים, בסתירה להיותו אוטומט סופי ולכן בהכרח L אינה רגולרית.

שימו לב: הפתרון משתמש בחזקה 4i למופעי a כדי להבטיח שחלוקת החזקה ב- 2 (2i למופעי b) תיתן בהכרח מספר זוגי!

 

חזרה

למאגר החומרים

לאתר מודלים חישוביים