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

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

רחלי צרניחוב

 

שאלה 1

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

             

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

 

פתרון

ניתן להציג את L בעזרת השפות הבאות מעל הא"ב {a,b,c,d}:

            } 1<n<4, m=2n L1  ={anbmï 

                 }  k mod 4 = 1 L2  ={ckï 

                  

L1∙( L2∙ L3)        = L

את L1 אפשר להציג בעזרת שתי השפותL4 = {a2b4}  ו- L5 = {a3b6} כך: L1= L4ÈL5.

L2 ו-L3 הן רגולריות, כי הנה אוטומטים מתאימים המקבלים אותן:

A2 עבור L2:

 

A3 עבור L3:

 

 

מסגירות משפחת השפות הרגולריות לשרשור גם L2∙L3 רגולרית.

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

ומסגירות משפות השפות הרגולריות לאיחוד גם  L4ÈL5רגולרית

ומסגירות משפות השפות הרגולריות לשרשור גם (L4ÈL5)∙(L2∙L3) = L1∙(L2∙L3) = L רגולרית.

 

שאלה 2

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

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

פתרון

L= L1ÇL2 כאשר L1 היא שפת כל המילים מעל הא"ב {a,b} אשר מכילות לכל היותר 9 אותיות a

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

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

 

(לא ניתן להשתמש בנימוק סופיות כי זו לא שפה סופית. למשל, היא מכילה את כל המילים ({biaïi³0}.

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

 

מסגירות משפחת השפות הרגולריות לחיתוך גם L= L1ÈL2 רגולרית.

 

שאלה 3

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

א. המילה מכילה את הרצף bcb וגם מסתיימת ברצף ccac.

ב. מספר האותיות b במילה גדול או שווה ל-2 וקטן או שווה ל-5 או שגם מספר האותיות c במילה גדול ממספר האותיות a במילה וגם מספר האותיות c במילה קטן מ-7.

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

 

פתרון

ניתן להציג את L בצורה הבאה:

      L = (L1ÇL2)È(L3ÈL4)

כאשר L1 היא שפת כל המילים מעל הא"ב {a,b,c} שמכילות את הרצף bcb,

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

L3 היא שפת כל המילים מעל הא"ב {a,b,c}שמספר האותיות b בהן גדול או שווה ל-2 וקטן או שווה ל-5,

L4 היא שפת כל המילים מעל הא"ב {a,b,c} שבהן מספר האותיות c גדול ממספר האותיות a ומספר האותיות c קטן מ-7.

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

 

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

 

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

 

(ניתן היה גם לפרק את L3 לשתי שפות רגולריות פשוטות ע"י שימוש בפעולת החיתוך).

 

L4 רגולרית – נשים לב ששפה זו היא למעשה השפה הבאה:

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

 

באוטומט זה המצב qij מציין כי נקראו i אותיות c ו-j אותיות a.

שימו לב – לא ניתן להיעזר בנימוק סופיות כי השפה אינה סופית.

בפרט היא מכילה את כל המילים {cbiïi³0}.

מסגירות משפחת השפות הרגולריות לחיתוך גם L1ÇL2 רגולרית.

מסגירות משפחת השפות הרגולריות לאיחוד גם L3ÈL4 וגם  L = (L1ÇL2)È(L3ÈL4) רגולריות.

 

שאלה 4

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

א. ניתן לחלק את המילה לשני חלקים כך שחלקה הראשון מכיל את הרצף bca וחלקה השני מכיל את הרצף acb.

ב. המילה מכילה את הרצף bb.

ג. המילה אינה מכילה יותר משלוש אותיות a רצופות.

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

 

פתרון

ניתן לייצג את L בעזרת השפות הבאות, כולן מעל הא"ב {a,b,c}:

L1 היא שפת כל המילים שמכילות את הרצף bca.

L2 היא שפת כל המילים שמכילות את הרצף bb.

L3 היא שפת כל המילים שמכילות את הרצף aaaa.

L1, L2 ו-L3 רגולריות:

A1 עבור L1:

 

A2 עבור L2:

 

A3 עבור L3:

 

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

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

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

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

וגם  רגולרית.

 

 

חזרה

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

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