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

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

ריקה רם

 

שאלה 1

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

L={ambncbp ïm+ℓ=n+p,m ³ n,n ³ 0,ℓ,p ³ 0 }

פתרון

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

נתבונן במילה aibi. מילה זו שייכת לשפה (n=ℓ=0, i=m=p) ולכן האוטומט מגיע מהמצב q למצב מקבל בקוראו את הסיפא  bi . לכן הוא מקבל את המילה aibj שאינה בשפה (ℓ=0, i=m ולכן m+ℓ=i וגם אם j מתפרש כ- n וגם אם הוא מתפרש כ- p עדיין n+p=j ן- i≠j). לכן בהכרח האוטומט מגיע למצב שונה על כל מילה ב- W, כלומר יש לו אינסוף מצבים, בסתירה להיותו אוטומט סופי. לכן L אינה רגולרית.

 

שאלה 2

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

L={akbnïk ³ 0,k<n<2k}

פתרון

נניח ש- L רגולרית ולכן קיים אוטומט סופי A שמקבל אותה. נתבונן בקבוצה האינסופית
W={an
ïn>1}. נניח שקיימות בקבוצה שתי מילים i>j>1, ai,aj כך שהאוטומט מגיע על ai ו- aj לאותו מצב q. נתבונן במילה ajbj+1  מילה זו שייכת לשפה כי j<j+1<2j ולכן האוטומט מגיע מהמצב q למצב מקבל בקוראו את הסיפא bj+1 . אבל אז נובע שגם המילה aibj+1  מתקבלת והיא אינה בשפה: i>j ולכן i ³ j+1 ולא מתקיים i<j+1<2i. מכאן שהאוטומט מגיע על כל מילה ב- W למצב שונה, כלומר יש לו אינסוף מצבים, בסתירה להיותו אוטומט סופי, לכן L אינה רגולרית.

 

חזרה

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

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