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

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

איריס ברגורי צור

 

שאלה 1

תהיינה  L1 ו-L2  שפות מעל הא"ב  {0,1}. תהי L2-L1 שפת כל המילים השייכות ל-L2 אך אינן שייכות ל-L1.

הוכח או הפרך (על ידי דוגמה נגדית) את הטענה הבאה:

אם L1 ו-L2-L1 רגולריות, אז L2 רגולרית.

 

פתרון

הטענה אינה נכונה.

דוגמה נגדית:

L1 היא שפת כל המילים שאורכן גדול מ-3.

L2={anbn ïn>0}.

L1 היא רגולרית (להוכחה מלאה יש כמובן להראות אוטומט סופי שמקבל את L1).

            L2 – L1 ={anbnïn>0, 2n<3}   

                  n=1} ={anbn ï 

 

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

 

שאלה 2

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

L1={anbmïn, m³1}

L2={anbnïn³1}

L3={anbmïn, m³1, n¹m}

 

א. הגדר את השפה L2 בעזרת L1 ו-L3, תוך שימוש בפעולות איחוד, חיתוך, משלים, שרשור והיפוך (חלק מהפעולות או כולן).

ב. נתון כי L1 רגולרית ו- L2אינה רגולרית.

    בהסתמך על הנתון, על סעיף א' ועל תכונות הסגירות של משפחת השפות הרגולריות, הוכח כי L3 אינה רגולרית.

 

פתרון

א.

 

ב. נניח בשלילה כי L3 רגולרית.

מסגירות משפחת השפות הרגולריות לפעולת המשלים נובע כי גם  רגולרית.

מהנתון (L1 רגולרית) ומסגירות משפחת השפות הרגולריות לחיתוך נובע

כי גם  רגולרית.

אבל  (ע"פ סעיף א')

ולכן קיבלנו כי L2 רגולרית, בסתירה לנתון.

לכן, ההנחה היתה שגויה ו-L3 אינה רגולרית.

 

חזרה

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

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