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

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

איריס ברגורי צור

 

שאלה 1

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

א. מספר האותיות b ב- w מתחלק ב-3 עם שארית 2.

ב. מספר האותיות c ב- w הוא כפול ממספר האותיות b ב- w.

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

פתרון

נניח בשלילה כי השפה רגולרית ולכן קיים אוטומט סופי A שמקבל אותה. נתבונן בקבוצת המילים W={b3n+2ïn ³ 0}. נראה שעל כל מילה בקבוצה W האוטומט A מגיע למצב שונה. נניח בשלילה כי קיימות שתי מילים ב-W  wi=b3i+2 ו- wj=b3j+2. כך ש- i≠j,  i,j ³ 0 והאוטומט A מגיע על wi ו- wj לאותו מצב q.

נתבונן במילה  b3i+2 c6i+4. אחרי קריאת הרישא b3i+2 מגיע האוטומט למצב q, ומשם עליו להגיע למצב מקבל עם סיום קריאת המילה כולה, כי המילה כולה שייכת לשפה 2×(3i+2)=6i+4), ולכן מספר האותיות c במילה כפול ממספר האותיות b, ומספר האותיות b במילה מתחלק ב- 3 עם שארית 2). מכאן נובע כי גם המילה  b3j+2 c6i+4 מובילה את האוטומט למצב מקבל, אבל מילה זו אינה בשפה (i ≠ j ולכן (6i+4 ≠2×(3j+2) , ולכן הגענו לסתירה. לכן בהכרח האוטומט A מגיע למצב שונה על כל מילה בקבוצה W. מאחר ש- W אינסופית, נובע מכאן של- A אינסוף מצבים, בסתירה להיותו אוטומט סופי. לכן הנחת השלילה הראשונה בהכרח שגויה, כלומר, השפה אינה רגולרית.

 

שאלה 2

לפניך שפות מעל הא"ב {a,b,c}. לכל אחת מהשפות קבע אם היא רגולרית או לא, והוכח את קביעתך.

א. השפה  {anbmckïn,m,k>0,k=2n+3}

ב. השפה  {anbmckïn,m,k>0,k=2n+m+3}

ג. השפה  {anbmckïn,m,k>0,k=2n-m+3,2n>m}

 

פתרון סעיף א

השפה אינה רגולרית. נניח בשלילה שהיא רגולרית ולכן קיים אוטומט סופי A שמקבל אותה. נתבונן בקבוצת המילים האינסופית W={anbïn>0}. נראה שעל כל מילה בקבוצה W האוטומט מגיע למצב שונה.  נניח בשלילה שקיימות בקבוצה שתי מילים  wi=aib ו- wj=ajb כך ש- i≠j, i,j>0 והאוטומט A מגיע על wj ו- wi לאותו מצב q. נתבונן במילה aibc2i+3. המילה שייכת לשפה ולכן האוטומט A מגיע עליה למצב מקבל. כלומר, קריאת הסיפא c2i+3 מובילה את האוטומט ממצב q למצב מקבל. אבל, מכאן נובע שהאוטומט A מקבל גם את המילה ajbc2i+3 שאינה שייכת לשפה. הגענו לסתירה ולכן הנחת השלילה השניה אינה נכונה – כלומר, לא קיימות מילים wi ו-wj כמפורט לעיל  ועל כל מילה בקבוצה W האוטומט מגיע למצב שונה. אך W אינסופית, ומכאן נובע של- A אינסוף מצבים בסתירה להיותו אוטומט סופי. לכן, גם הנחת השלילה הראשונה שגויה והשפה אינה רגולרית.

 

פתרון סעיף ב

השפה אינה רגולרית. שוב נניח בשלילה שהיא רגולרית ונסיק את קיומו של אוטומט סופי A שמקבל אותה. נתבונן באותה קבוצה אינסופית W={anbïn>0} ונראה ש- A מגיע למצב שונה על כל מילה ב-W. נניח בשלילה שקיימות שתי מילים wi=aib ו- wj=ajb כך ש- i≠j,   i,j>0 ו-A מגיע על wi ו- wj לאותו מצב q. עתה נתבונן במילה aibc2i+4. מילה זו שייכת לשפה כי 2i+4=2i+1+3. לכן מהמצב q האוטומט מגיע עם קריאת הסיפא c2i+4 למצב מקבל. אבל, מכאן נובע שגם המילה ajbc2i+4 מובילה את האוטומט למצב מקבל, למרות שאינה בשפה. הגענו לסתירה ולכן הנחת השלילה השניה אינה נכונה – כלומר, על כל מילה ב- W האוטומט A מגיע למצב אחר. מכאן נובע של- A אינסוף מצבים בסתירה להיותו אוטומט סופי. לכן הנחת השלילה הראשונה בהכרח שגויה ולכן השפה אינה רגולרית.

 

פתרון סעיף ג

גם שפה זו אינה רגולרית. גם הפעם נניח בשלילה שהיא רגולרית ונסיק מכאן את קיומו של אוטומט סופי A שמקבל אותה. נתבונן הפעם בקבוצת המילים האינסופית W={anb3ïn>1} ונראה כי על כל מילה בקבוצה זו האוטומט מגיע למצב שונה. נניח בשלילה כי קיימות שתי מילים wi=aib3 ו- wj=ajb3 כך ש- i,j>1 , i≠j והאוטומט A מגיע על wi ו- wj לאותו מצב q. נתבונן במילה aib3c2i. מילה זו שייכת לשפה כי 2i=2i-3+3 ו- 2i>3 (i ³ 2 ולכן 2i ³ 4 כלומר 2i>3). לכן האוטומט A מגיע עליה למצב מקבל. כלומר, קריאת הסיפא c2i מהמצב q מובילה את A למצב מקבל. אבל מכאן נובע כי גם המילה ajbc2i מביאה את A למצב מקבל, למרות שאינה בשפה. הגענו לסתירה ולכן בהכרח A מגיע למצב שונה על כל מילה ב-W. מכאן נובע של-A אינסוף מצבים, בסתירה להיותו אוטומט סופי. סתירה זו מביאה למסקנה שהנחת השלילה הראשונה היתה שגויה. כלומר, השפה אינה רגולרית.

 

חזרה

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

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