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

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

אסנת אנגלמן, אסתי מאסטראסי, אורנה אברך-שטיין

 

שאלה 1

הוכח ששפת כל המילים מעל הא"ב {0,1,2,…9} המייצגות מספרים שמתחלקים ב-12 ללא שארית היא שפה רגולרית.

 

פתרון

השפה הנתונה ניתנת לפירוק באופן הבא: L1ÇL2

כאשר L1 היא שפת כל המילים מעל הא"ב {0,1,2,…9} המייצגות מספרים שמתחלקים ב-4 ללא שארית ו-L2 היא שפת כל המילים מעל הא"ב {0,1,2,…9} המייצגות מספרים שמתחלקים ב-3 ללא שארית.

L1 ו- L2הן שפות רגולריות. אוטומט סופי המקבל את L1 נתון באיור 2.13 ג' בספר לתלמיד. אוטומט עבור L2 פועל ע"פ עקרון דומה. יש לו חמישה מצבים:

q0 – מצב התחלתי.

q1 – זוכר שארית 1 בחלוקה ב-4.

q2 – זוכר שארית 2 בחלוקה ב-4.

q3 – זוכר שארית 3 בחלוקה ב-4.

q4 – מצב מקבל, זוכר שארית 0 בחלוקה ב-4.

 

 

אפשר, כמובן, להגדיר שפות נוספות על אותו עקרון – כמו שפת כל המילים מעל הא"ב {0,1,2,…9} המייצגות מספר שמתחלק ב-20 ולהשתמש במקרה זה בשפת כל המילים מעל הא"ב הזה המייצגות מספר שמתחלק ב-5 ושפת כל המילים מעל הא"ב הזה המייצגות מספר שמתחלק ב-4.

 

שאלה 2

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

 

פתרון

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

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

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

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

השפה הנדונה היא

(וניתן להציגה גם כ-).

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

 

אוטומטים דומים מקבלים את  L2 ו-L3.

עבור L2 נחליף את a במעברים מ-q0 ל-q1 ומ- q1ל-q2 ב-b,

ועבור L3 נחליף את a במעברים האלו ב-c. לכן גם L2 ו-L3 רגולריות.

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

בייצוג השני מקבלים כי השפה הנדונה רגולרית ע"י שימוש פעמיים בתכונת הסגירות של השפות הרגולריות לפעולת האיחוד ופעם אחת שימוש בתכונת הסגירות של השפות הרגולריות לפעולת המשלים.

 

שאלה 3

האם השפה L={(010)n(001)m ïn, m³0} היא רגולרית?

הוכח את תשובתך.

 

פתרון

L = L1∙L2

כאשר    L1={(010)nïn³0}

           L2={(001) mïm³0}

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

 

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

 

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

 

שאלה 4

תהי L שפת כל המילים מעל הא"ב {a,b} המתחילות ברצף לא ריק של אותיות a ומסתיימות ברצף אותיות b שארוך מהרצף הפותח או שהן מורכבות מחזרה מספר כלשהו (גדול מ-0) של פעמים על הרצף ab. האם L רגולרית? הוכח את תשובתך.

 

פתרון

ניתן להציג את L באופן הבא: L = L1ÈL2.

L1 מעל הא"ב {a,b}:

{w מעל a,b}} ,m>n>0 L1={anwbmï

L2 מעל הא"ב {a,b}:

            } j >0 L2={(ab)j |

L2 רגולרית.

הנה אוטומט סופי שמקבל אותה:

 

L1 אף היא רגולרית.

נשים לב כי למעשה משמעות הדרישה היא שהמילה תתחיל באות a ותסתיים ב-2 אותיות b. אם המילה מתחילה ביותר מאות a אחת ניתן לצרף את האותיות העודפות לתוך המילהw   וכך בכל מקרה לא מופר התנאי m>n. לכן אוטומט מתאים הוא האוטומט הלא דטרמיניסטי הבא:

 

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

ניתן גם לפרק את L1 לחיתוך שפת כל המילים המתחילות ב-a ושפת כל המילים המסתיימות ב-bb.

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

{w מעל a,b}}, אינה מתחילה ב-a ואינה מסתיימת ב-b ,m>n>0 L'1={anwbmï

וזו שפה חופשית הקשר, שאינה רגולרית.

 

חזרה

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

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