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

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

אלה פוק

 

שאלה 1

האם השפה L={a2k(ba)m(ab)nïn,m ³ 0,m≠n+k,k>0}  היא שפה רגולרית? הוכח את תשובתך.

פתרון

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

נתבונן בקבוצת המילים האינסופית W={a2 (ba)mï m ³ 1 }.

נניח שקיימות בקבוצה זו שתי מיליםa2(ba)i  ו- a2(ba)j כך ש i≠j, i,j ³ 1 ו-A מגיע על שתי המילים האלו לאותו מצב q.

נתבונן  במילה a2(ba)i (ab)j-1 . מילה זו שייכת לשפה: k=1, i ³ 1, ובפרט i ³ 0 , j ³ 1 ולכן j-1 ³ 0 ו- i¹j-1+k=j-1+1=j. לכן האוטומט צריך להגיע מהמצב q עם קריאת הסיפא (ab)j-1 למצב מקבל. אבל אז האוטומט מקבל גם את המילה a2(ba)j (ab)j-1  . מילה זו אינה בשפה כי j-1+k=j-1+1=j, לכן בהכרח האוטומט חייב להגיע למצב שונה על כל מילה ב- W ומכאן שיש לו אינסוף מצבים, בסתירה להיותו אוטומט סופי. לכן בהכרח L אינה רגולרית.

 

שאלה 2

האם השפה L={a2nb2k(ab)tamïk,n,t,m ³ 0,t=k} היא רגולרית? הוכח את תשובתך.

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

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

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

 

חזרה

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

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