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

לפניכם ארבעה סעיפים (1)-(4). ענו על כולם (בנימוק מספיק הסבר מילולי, אין צורך באוטומט).

(1) בנוגע לכל אחת מן השפות L₃ - L₁, כתבו אם היא רגולרית או לא רגולרית. נמקו את תשובתכם.

(2) האם השפה L₁ ∩ L₃ רגולרית? נמקו את תשובתכם.

(3) האם השפה L₁ ∩ המשלים של L₃ רגולרית? נמקו את תשובתכם.

(4) האם השפה L₂ ∩ המשלים של L₃ רגולרית? נמקו את תשובתכם.

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

הסבר

השפה L מכילה מילים שבהן כל אחת מן האותיות abc מופיעה פעם אחת לפחות, ולפי סדר זה (המופעים של a תחילה ואחר כך של b ואחר כך של c). כמו כן, אם מספר המופעים של האות a הוא זוגי/אי־זוגי, מספר המופעים של האות b או של האות c יהיה גם הוא זוגי/אי־זוגי בהתאמה.

✎ דוגמה למילה בשפה L

abbbbccc, כי כל אחת מן האותיות abc מופיעה בה, ולפי הסדר הנדרש. כמו כן מספר המופעים של האות a הוא אי־זוגי, וכך גם מספר המופעים של האות c.

✎ דוגמה נוספת למילה בשפה L

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

✎ דוגמה למילה שאינה בשפה L

aabc. אומנם כל אחת מן האותיות abc מופיעה בה, ולפי הסדר הנדרש, אך מספר המופעים של האות a הוא זוגי, ואילו מספר המופעים של האות b ושל האות c הוא אי־זוגי.

(1) לפניכם חמש מילים: abbac, abc, bbc, abcc, abbcc.

העתיקו כל אחת מן המילים למחברתכם, וקבעו אם היא שייכת לשפה L או לא שייכת לשפה L. נמקו את קביעותיכם.

(2) נתון לפניכם אוטומט סופי דטרמיניסטי שאינו מלא המקבל את השפה L. באוטומט קיימים כל המצבים וכל המעברים הנדרשים, אך בכמה מן המעברים חסרים סימני הקלט (התווים במעברים), והמצבים המקבלים באוטומט אינם מסומנים כלל.

העתיקו את האוטומט למחברתכם, הוסיפו את סימני הקלט החסרים, וסמנו את המצבים המקבלים.

⚠ הערה — אילוץ מחייב

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