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

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

ויקטוריה צורי

 

שאלה 1

תהי L שפת כל המילים מעל הא"ב {0,1,2}, שמתחילות במספר כלשהו (גדול ממש מ-0) של אפסים ואין בהן שתי אותיות 1 צמודות.

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

 

פתרון

קל יותר לפתור שאלה זו בעזרת פירוק לשפות פשוטות יותר ושימוש בתכונות סגירות, אך גם פתרון ישיר, על ידי בניית אוטומט הוא אפשרי. בפתרון ישיר לעיתים קרובות תלמידים שוכחים לטפל באות 2.

ניתן לפרק את L כך:   מעל הא"ב {0,1,2}:

{w מתחילה ברצף לא ריק של אפסים ï  L1={w  

{w מכילה רצף 11 ï  L2={w  

L1 רגולרית – הנה אוטומט שמקבל אותה (אוטומט דטרמיניסטי לא מלא)

 

L2 רגולרית – הנה אוטומט שמקבל אותה (אוטומט לא דטרמיניסטי):

 

מסגירות משפחת השפות הרגולריות לפעולת המשלים גם  רגולרית,

ומסגירות משפחת השפות הרגולריות לפעולת החיתוך גם  רגולרית.

הערה: אם השאלה ניתנת לפני הוראת פרק 4, יש כמובן לתת אוטומטים דטרמיניסטיים להוכחת רגולריות L1 ו-L2 .

הנה אוטומט מתאים עבור L1:

 

והנה אוטומט מתאים עבור L2:

 

שאלה 2

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

1. מתחילות ומסתיימות באותה אות.

2. מכילות את הרצף aa.

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

 

פתרון

פתרון ישיר ללא שימוש בפירוק (ע"י בניית אוטומט סופי המקבל את השפה) אינו פשוט,

אך ניתן להגיע לפתרון בעל מורכבות טכנית נמוכה ע"י שימוש בפירוק הבא:

L  = L1Ç(L2 ÈL3)  כאשר L1, L2 ו-L3 מעל {a,b,c}:

{w באורך אי-זוגי ï  L1={w  

  {w מתחילה ומסתיימת באותה אות ï  L2={w  

    {w מכילה את הרצף aa ï  L3={w  

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

 

הנה אוטומט סופי שמקבל את L2:

 

זהו אוטומט סופי לא דטרמיניסטי.

אוטומט דטרמיניסטי עבור שפה זו הוא מורכב למדי, ולכן שאלה זו טובה כדי לעודד שימוש באי-דטרמיניזם (ומתאימה אחרי סיום תהליך ההוראה של פרק 4).

q1 מטפל במקרה המיוחד שהמילה בת אות אחת – כלומר האות המתחילה היא גם האות המסיימת (כמובן, אפשר לאחד את  q1ו-q5).

הנה אוטומט סופי שמקבל את L3:

 

לכן L1, L2 ו- L3הן שפות רגולריות.

מסגירות משפחת השפות הרגולריות לפעולת האיחוד

גם L2ÈL3 רגולרית ומסגירות משפחת השפות הרגולריות לפעולת החיתוך גם (L2 ÈL3)L1Ç היא רגולרית.

שאלה זו מתאימה הן לעבודת כיתה, הן לשיעורי בית והן למבחן.

המורה יכול/ה להיעזר בה כדי לבדוק את מידת השליטה של התלמידים במנגנון הלא דטרמיניסטי ואת נטייתם לפתרונות המשתמשים בפירוק (לעומת פתרונות ישירים).

 

שאלה 3

נתבונן בשפה מעל הא"ב {0,1,2}, המכילה את כל המילים שמתחילות ברצף 01 או ברצף 10, ומסתיימות ברצף 10 או ברצף 0111.

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

 

פתרון

פתרון ישיר שאינו משתמש בפירוק אינו פשוט, כי קל לשכוח מילים כמו 10, 0111 או 10111 שהן בשפה ומקיימות תנאים בחפיפה. כמובן, כאשר מפרקים את השפה לשפות פשוטות, ההתמודדות היא עם כל תנאי בנפרד ואין צורך לחשוב על שילוב התנאים.

השאלה מתאימה אחרי סיום תהליך ההוראה של פרק 4, כי שימוש באי-דטרמיניזם מפשט באופן משמעותי את המורכבות הטכנית של הפתרון, ובנוסף, אז ניתן להשתמש בפעולת ההיפוך.

ניתן להציג את השפה באופן הבא, כאשר L1, L2 ו- L3הן מעל הא"ב {0,1,2}.

(L1ÈL2)Ç(R(L1)ÈL3)

 {w מתחילה ב-01 |  L1={w  

 {w מתחילה ב-10 |  L2={w  

        {w מסתיימת ב-0111 |  L3={w  

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

 

L2 היא רגולרית – הנה אוטומט סופי המקבל אותה:

 

L3 היא רגולרית – הנה אוטומט סופי המקבל אותה:

 

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

מסגירות משפחת השפות הרגולריות לפעולת האיחוד גם L1ÈL2 ו-R(L1)ÈL3 רגולריות,

ומסגירות משפחת השפות הרגולריות לפעולת החיתוך גם    (L1ÈL2)Ç(R(L1)ÈL3)רגולרית.

 

 

חזרה

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

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