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

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

אתי מנשה

 

שאלה 1

האם השפה L={aibjcdkïi ³ 0,k > j ³ 0} היא רגולרית? הוכח את תשובתך!

פתרון

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

נסתכל על קבוצת המילים W={bnïn ³ 0}. נניח בשלילה שקיימות בקבוצה זו שתי מילים bi ו- bj  i<j שעליהן האוטומט מגיע לאותו מצב q. נסתכל על המילה bicdj. מילה זו שייכת לשפה (מספר האותיות a שווה ל-0, מספר האותיות d גדול ממש ממספר האותיות b), לכן האוטומט מגיע למצב מקבל בקוראו את הסיפא cdj מהמצב q. אבל מכאן נובע שהוא מקבל גם את המילה bjcdj שאינה שייכת לשפה, כי מספר האותיות d בה אינו גדול ממספר האותיות b שבה. לכן בהכרח האוטומט A מגיע למצב שונה עבור כל מילה ב- W ומאחר ש-W אינסופית, נובע של-A אינסוף מצבים, בסתירה להיותו אוטומט סופי. לכן L אינה רגולרית.

 

שאלה 2

תהי L2 שפה מעל הא"ב {a,b} אשר ידוע כי אינה רגולרית. נסמן ב- *S את שפת כל המילים מעל הא"ב {a,b}.

הוכח שהשפה L=R(S*-L2) אינה רגולרית.  

פתרון

נניח בשלילה ש- L רגולרית. מסגירות משפחת השפות הרגולריות לפעולת ההיפוך נובע שגם R(L) רגולרית.

אבל  R(L)=R(R(S*-L2)= S*-L2. כעת, S*-L2 היא שפת כל המילים שאינן ב- L2, כלומר .

ובמילים אחרות .

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

 

חזרה

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

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