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

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

דורון זוהר

 

שאלה 1

א. נתונות שתי שפות מעל הא"ב {a,b,c}:

L1 היא שפת כל המילים המתחילות ב-a.
L2 היא שפת כל המילים המתחילות ב-b.
נתון כי
L1 ו-L2 רגולריות. הוכח, תוך שימוש בנתון ובתכונות סגירות, כי L3  אף היא רגולרית, כאשר L3 היא שפת כל המילים מעל הא"ב {a,b,c} המתחילות ב-c.

ב. לפניך הגדרות שונות של L3  בעזרת L1 ו-L2 אשר הוצעו ע"י תלמידים תוך ניסיון לפתור את סעיף א'.

לכל הגדרה קבע אם היא נכונה או שגויה, ואם היא שגויה (כלומר אינה שווה ל-L3) כתוב איזו שפה היא יוצרת.

 

I

 

 

II

 

 

III

 

 

IV

 

 

V

 

L1ÇL2

 

פתרון

סעיף א' של השאלה מתאים כשיעורי בית או כשאלה בבחינה. כדאי להפריד ממנו את סעיף ב' ולתת אותו אח"כ כבסיס לעבודת כיתה (וכמובן שאם תוך פתרון סעיף א' נתנו התלמידים פירוקים אחרים ל-L3 כדאי לדון גם בהם).

 

פתרון לסעיף א'

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

כלומר .

מאחר שנתון ש-L1 ו-L2 רגולריות, ומאחר ש-{e} סופית, ולכן גם כן רגולרית,

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

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

וגם  רגולרית.

 

פתרון לסעיף ב'

I     המילים שאינן מתחילות ב-a ואינן מתחילות ב-b הן או המילה הריקה או מילים שמתחילות ב-c, ולכן אין זו השפה המבוקשת

(המילה הריקה שייכת לשפה  

אך לא לשפה L3).

II    אין מילים ששייכות ל-L1ÇL2 משום שאין מילה שגם מתחילה ב-a וגם מתחילה ב-b.

לכן L1ÇL2 היא השפה הריקה ושפת המשלים שלה היא שפת כל המילים מעל הא"ב {a,b,c}.

III   השפה  היא שפת כל המילים שמתחילות ב-a או מתחילות ב-b או שהן המילה הריקה.

משלימתה היא לכן שפת כל המילים שמתחילות ב-c כלומר L3

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

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

משום שאם מילה מתחילה ב-a אז היא אינה מתחילה ב-b

ואם מילה מתחילה ב-b אז היא אינה מתחילה ב-a

וכמובן המילה הריקה או מילה שמתחילה ב-c אינה מתחילה ב-a וגם אינה מתחילה ב-b

ולכן כל מילה מקיימת לפחות את אחד משני התנאים (שוב ניתן להגיע לכך גם מכללי דה-מורגן וסעיף II).

V    כאמור בסעיף II,  L1ÇL2 היא השפה הריקה Ø.

 

שאלה 2

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

החלק הראשון מתחיל ברצף ab ואחריו הוא מכיל מספר זוגי של אותיות a או מספר אותיות b המתחלק ב-3 ללא שארית.

החלק השני מסתיים ברצף cbba ובין שני החלקים מפריד הרצף c3.

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

 

פתרון

ניתן להגדיר את השפה באופן הבא:

 L4∙L5) ((L1∙(L2ÈL3)) כאשר L1 היא השפה {ab},

L2 היא שפת כל המילים המכילות מספר זוגי של אותיות a,

L3 היא שפת כל המילים שמספר האותיות b בהן מתחלק ב-3 ללא שארית,

L4 היא השפה {c3} ו-L5 היא שפת כל המילים שמסתיימות ברצף cbba.

כל השפות מעל הא"ב {a,b,c}.

כל השפות רגולריות.

 

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

A2 עבור L2:

 

A3 עבור L3:

 

A5 עבור L5:

 

L1 ו-L4 סופיות ולכן רגולריות.

מסגירות משפחת השפות הרגולריות לפעולת האיחוד גם L2ÈL3 רגולרית.

מסגירות משפחת השפות הרגולריות לפעולת השרשור גם ( L1 ∙(L2ÈL3 רגולרית,

גם L4∙L5 רגולרית וגם L4∙L5)))∙(L1∙(L2ÈL3) רגולרית.

 

חזרה

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

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