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

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

דגנית מורן

 

שאלה 1

תהי L השפה הבאה מעל הא"ב {a,b,c}:

L={anbmckïk=n-m, n > m ³ 0}

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

פתרון

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

נתבונן בקבוצת המילים האינסופית W={anïn>0}.

נניח שקיימות בקבוצה זו שתי מילים, i≠j, aj, ai כך שהאוטומט מגיע על שתיהן לאותו מצב q.

נתבונן במילה aici. מילה זו שייכת לשפה (k=n, m=0, n=i>0) ולכן האוטומט מגיע למצב מקבל בקוראו את הסיפא ci מהמצב q. לכן האוטומט מקבל גם את המילה aicj אך זו אינה שייכת לשפה. לכן בהכרח האוטומט A מגיע למצב שונה על כל מילה ב- W, ומאחר ש-W אינסופית, נובע שיש לו אינסוף מצבים, בסתירה להיותו אוטומט סופי. לכן L אינה רגולרית.

 

שאלה 2

תהי L השפה הבאה מעל הא"ב {a,b,c}:

L={ckabnanbïk,n ³ 0}

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

פתרון

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

נתבונן בקבוצת המילים האינסופית W={abnïn ³ 0} ונניח שקיימות בקבוצה זו שתי מילים i≠j, abj,abi כך שהאוטומט מגיע על שתיהן לאותו מצב q. נתבונן במילה abiaib. מילה זו שייכת לשפה (k=0,n=i) ולכן האוטומט מגיע למצב מקבל בקוראו את הסיפא aib מהמצב q. לכן האוטומט מקבל גם את המילה abjaib שאינה בשפה. לכן בהכרח A מגיע למצב שונה על כל מילה ב- W ומאחר ש- W אינסופית, נובע שיש לו אינסוף מצבים, בסתירה להיותו אוטומט סופי. לכן L אינה רגולרית.

 

חזרה

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

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