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

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

דגנית מורן

 

שאלה 1

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

האות לפני האחרונה במילה היא a, המילה מכילה פעמיים את הרצף abc ומספר האותיות b במילה הוא זוגי.

א. הבא דוגמה למילה השייכת לשפה ודוגמה למילה שאינה שייכת לשפה.

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

 

פתרון

א. המילה  cabcccabcaa שייכת לשפה.

    המילה abcabcabc אינה שייכת לשפה.

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

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

L2 – שפת כל המילים בהן מספר האותיות b זוגי.

L3 – שפת כל המילים בהן האות לפני האחרונה היא a.

כעת L = (L1∙L1)ÇL2ÇL3

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


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


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



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

מסגירות משפחת השפות הרגולריות לחיתוך גם L2ÇL3 רגולרית וגם (L = (L1∙L1)Ç(L2ÇL3.

 

שאלה 2

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

אשר מתחילות ברצף מהצורה anb n>0)), אינן מכילות a בהמשכן, והאות לפני האחרונה בהן היא b.

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

 

פתרון

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

L1={anbïn>0}

L2 – שפת כל המילים שאינן מכילות a.

L3 – שפת כל המילים בהן האות לפני האחרונה היא b.

      L = (L1∙L2)ÇL3

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

 

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

 

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

 

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

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

ניתן כמובן להוכיח כי L רגולרית גם על ידי בנייה ישירה של אוטומט המקבל אותה. אם מנצלים את המנגנון האי-דטרמיניסטי האוטומט המתאים אינו מאוד מורכב.

 

בכל זאת יש סיכוי לא מבוטל לטעות בבנייה ישירה.

למשל, יתכן כי תלמיד לא יקח בחשבון כי b המסיימת את הרצף הפותח anb יכולה גם להיות האות הלפני אחרונה במילה.

 

שאלה 3

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

א. מתחילות ברצף ab ומכילות cc.

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

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

 

פתרון

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

L2 – שפת כל המילים שמכילות cc,

L3 שפת כל המילים שמכילות bbc.

      L = (L1∙L2)ÈL3

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

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

 

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

 

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

 

חזרה

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

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