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

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

לאה יעקובוביץ

 

שאלה 1

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

 

פתרון

תרגיל זה דומה מאוד לשאלה של אלה פוק בבעיות המשולבות.

L היא למעשה השפה

כאשר L1 היא שפת כל המילים מעל הא"ב {a,b} בהן מספר האותיות a זוגי

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

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

 

L2 רגולרית כי אוטומט שמקבל אותה מתקבל מהאוטומט האחרון ע"י החלפת כל a ב-b וכל b ב-a.

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

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

ו-  רגולריות

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

ניתן כמובן להוכיח ש-L רגולרית ע"י בנייה ישירה של אוטומט. במקרה זה מדובר באוטומט בן 4 מצבים (עבור כל צירוף של זוגיות מספר אותיות a וזוגיות מספר אותיות b)

 

חזרה

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

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