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

תכונות סגירות של שפות רגולריות

אתי מנשה

 

שאלה 1

תהי L שפת כל המילים מעל הא"ב {a,b} שאינן מתחילות ב-a, מכילות שתי אותיות b ואינן מסתיימות ב-a.

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

 

פתרון

נגדיר את שפת הבסיס הבאה מעל הא"ב {a,b}:

L1 – שפת כל המילים שמתחילות ב-b.

ברור כי L1 רגולרית כי הנה אוטומט סופי שמקבל אותה:

 

מסגירות משפחת השפות הרגולריות לפעולת ההיפוך גם R(L1) רגולרית וזוהי שפת כל המילים שמסתיימות ב-b.

השפה L היא השפה הבאה L1∙ R(L1).

נשים לב כי מילים ב-L1 מכילות לפחות b אחת וכך גם מילים ב-R(L1)

ולכן מילים בשפה L1∙R(L1) מכילות לפחות שתי אותיות b.

ברור כי מילים בשפה זו מתחילות ב-b ומסתיימות ב-b ולכן הן אינן מתחילות ב-a ואינן מסתיימות ב-a.

כדאי לשים לב כי שפת כל המילים שאינן מתחילות ב-a אינה שפת כל המילים שמתחילות ב-b, כי המילה הריקה שייכת לשפה הראשונה ולא לשנייה, אך במקרה זה, בגלל שמילה בשפה L חייבת להכיל לפחות שתי אותיות b היא אינה יכולה להיות ריקה ולכן אנו יכולים להשתמש בפעולות שרשור ולהתעלם מהמילה הריקה.

אפשרות פירוק אחרת היא ע"י שתי שפות:

שפת כל המילים שאינן מתחילות ב-a (L2)

ושפת כל המילים שמכילות שתי אותיות b (L3) ואז L = L2ÇL3ÇR(L2).

המורכבות הטכנית שמשרה הפתרון הזה היא מעט יותר גדולה.

כמובן, אפשר גם להשתמש בשפת המילים שמתחילות ב-a (L4)

ובפירוק .

המורכבות הטכנית של הפתרון הזה דומה לזו של הפתרון לשאלה האחרונה של רחלי צרניחוב.

 

חזרה

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

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