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

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

ריקה רם

 

שאלה 1

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

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

 

פתרון

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

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

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

L1 היא סופית ולכן רגולרית. L2 אף היא רגולרית (מוכח בספר לתלמיד).

L=L1∙L2∙L1.

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

שאלה זו מדגימה יפה כי השימוש בפירוק יכול להפחית בצורה משמעותית את המורכבות הטכנית של הפתרון, ובמקרה זה אפילו אין צורך לבנות אוטומט, בעוד שבניית אוטומט ישיר לשפה כלל אינה טריוויאלית.

 

חזרה

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

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