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

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

דורון זוהר

 

שאלה 1

נתבונן בשפת כל המילים מעל הא"ב {a,b,c} המקיימות לפחות אחד משני התנאים הבאים:

א. אורך המילה זוגי וגדול מ- 0 ומספר מופעי האות a קטן מ- 100.

ב. ניתן לחלק את המילה לשני חלקים כך שבחלק הראשון מספר האותיות b גדול או שווה למספר האותיות c

    ובחלק השני מספר האותיות a גדול או שווה למספר האותיות c.

האם השפה רגולרית? הוכח את תשובתך.

פתרון

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

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

נניח שקיימות בקבוצה זו שתי מילים ai ו- aj  כך ש- 100 £ i < j והאוטומט מגיע על ai ו- aj  לאותו מצב q. המילה  aici בשפה כי היא מקיימת את תנאי ב: ניתן לחלק אותה כך e·aici. בחלק הראשון מספר האותיות b שווה למספר האותיות c (השווה ל-0) ובחלק השני מספר האותיות a שווה למספר האותיות c. לכן מהמצב q עם קריאת הסיפא ci האוטומט מגיע למצב מקבל. אבל מכאן נובע שהוא מקבל גם את המילה  aicj . מילה זו אינה בשפה: היא אינה מקיימת את תנאי א' כי מספר האותיות a בה אינו קטן מ- 100 והיא גם אינה מקיימת את תנאי ב' כי בכל דרך שבה מחלקים את המילה תמיד בחלק השני מספר האותיות a קטן ממספר האותיות c. לכן בהכרח האוטומט מגיע על כל מילה ב- W למצב שונה ומכאן נובע כי יש לו אינסוף מצבים בסתירה להיותו אוטומט סופי. לכן, בהכרח השפה אינה רגולרית.

זו שאלה מעניינת בגלל התוספת של סעיף א' המחייבת הגדרה זהירה של הקבוצה W.

 

שאלה 2

נתבונן בשפת כל המילים מעל הא"ב {0,1} המקיימות לפחות אחד משני התנאים הבאים:

א. המילה מסתיימת ברצף 10 ואורכה זוגי וגדול מ- 0.

ב. ניתן לחלק את המילה כך שבחלק הראשון מספר האותיות 0 גדול ממספר האותיות 1

    ובחלק השני מספר האותיות 1 גדול או שווה למספר האותיות 0 ובין שני החלקים מפריד הרצף 0110.

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

פתרון

בדומה לשאלה 1, גם כאן, בגלל התוספת של סעיף א', יש לוודא שהמילה שנוצרת אחרי הדבקת אחת הסיפות לרישא מ- W אינה בשפה (בגלל שהיא עומדת בתנאי סעיף א').

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

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

נניח שקיימות בקבוצה זו שתי מילים 0i01100i ו- 0j01100j כך ש- i>j>0 והאוטומט מגיע על שתיהן לאותו מצב q.

נתבונן במילה 0i01100i1i . היא בשפה כי ניתן לחלקה כך:0i×0110·0i1i  ואז בחלק הראשון מספר האותיות 0 הוא 0<i וזה גדול ממספר האותיות 1 השווה ל-0, ובחלק השני מספר האותיות 1 שווה למספר האותיות 0 ובין שני החלקים מפריד הרצף 0110. לכן מהמצב q האוטומט מגיע למצב מקבל עם קריאת הסיפא  1i , ולכן נובע כי האוטומט מקבל גם את המילה 0i01100j1i  i>j>0. מילה זו אינה בשפה – היא אינה מקיימת את סעיף א' כי אינה מסתיימת ב- 10. היא גם אינה מקיימת את סעיף ב' כי יש רק חלוקה אפשרית אחת לשני חלקים שביניהם מפריד הרצף 0110:  0i·0110·0j1i ואז בחלק השני מספר האותיות 1 קטן ממספר האותיות 0. לכן, בהכרח האוטומט מגיע למצב שונה על כל מילה ב- W ומאחר ש- W אינסופית, נקבל מכאן כי לאוטומט אינסוף מצבים, בסתירה להיותו אוטומט סופי. לכן בהכרח השפה אינה רגולרית.

 

שאלה 3

נתבונן בשפת כל המילים מעל הא"ב {a,b,c} אשר מספר האותיות a בהן כפול ממספר האותיות b והן מכילות את הרצף bc.

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

פתרון

נניח שהשפה רגולרית ולכן קיים אוטומט סופי A שמקבל אותה. נתבונן בקבוצת המילים האינסופית הבאה: W={bncïn>0}. נניח שקיימות בקבוצה זו שתי מילים bic ו- bjc כך ש- i≠j שהאוטומט מגיע עליהן לאותו מצב q. נתבונן במילה bica2i. מילה זו שייכת לשפה כי היא מכילה את הרצף bc ומספר האותיות a בה כפול ממספר האותיות b. לכן האוטומט מגיע מהמצב q למצב מקבל בקוראו את הסיפא a2i. אבל, מכאן נובע שהוא מקבל גם את המילה bica2j, שאינה שייכת לשפה כי מספר האותיות  a  בה אינו כפול ממספר האותיות b שבה. לכן בהכרח האוטומט מגיע למצב שונה על כל מילה ב- W ומאחר ש- W אינסופית, נובע מכך שיש לו אינסוף מצבים, בסתירה להיותו אוטומט סופי. לכן בהכרח השפה אינה רגולרית.

 

חזרה

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

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