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

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

לאה יעקובוביץ

 

שאלה 1

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

L={anbmïn,m>=0,m¹n}

פתרון

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

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

נניח שקיימות בקבוצה זו שתי מלים i≠j, ai,aj  כך ש-A מגיע על שתיהן לאותו מצב q. נתבונן במילה aibj  . היא שייכת לשפה ולכן A מגיע למצב מקבל בקוראו את הסיפא bj  מהמצב q. אבל מכאן נובע שהאוטומט מקבל גם את המילה aibi שאינה בשפה. לכן בהכרח האוטומט A מגיע למצב שונה על כל מילה ב- W ולכן יש לו אינסוף מצבים בסתירה להיותו אוטומט סופי. לכן בהכרח L אינה רגולרית.

 

חזרה

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

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