בשאלה זו שני סעיפים, א–ב, שאין קשר ביניהם. ענו על שני הסעיפים.
סעיף א. לפניכם שלוש שפות מעל הא"ב {a , b}:
- L1 = { aⁿbᵐaᵏ | n, m, k > 0, n = k }
- L2 = { aⁿbᵐaᵏ | n, m, k > 0, n % 2 = k % 2 }
- L3 = { aⁿbᵐaᵏ | n, m, k > 0, n+m+k < 100 }
סעיף ב. נתונה השפה L מעל הא"ב {a,b,c}:
L = { aᵐbᵏcˣ | m, k, x > 0 וגם (m%2 = k%2 או m%2 = x%2) }
הסבר: השפה L מכילה מילים שבהן כל אחת מן האותיות abc מופיעה פעם אחת לפחות, ולפי סדר זה (המופעים של a תחילה ואחר כך של b ואחר כך של c). כמו כן, אם מספר המופעים של האות a הוא זוגי/אי־זוגי, מספר המופעים של האות b או של האות c יהיה גם הוא זוגי/אי־זוגי בהתאמה.
דוגמה למילה בשפה L היא abbbbccc, כי כל אחת מן האותיות abc מופיעה בה, ולפי הסדר הנדרש. כמו כן מספר המופעים של האות a הוא אי־זוגי, וכך גם מספר המופעים של האות c.
דוגמה נוספת למילה בשפה L היא aaaabbc, כי כל אחת מן האותיות abc מופיעה בה, ולפי הסדר הנדרש. כמו כן מספר המופעים של האות a הוא זוגי, וכך גם מספר המופעים של האות b.
דוגמה למילה שאינה בשפה L היא aabc. אומנם כל אחת מן האותיות abc מופיעה בה, ולפי הסדר הנדרש, אך מספר המופעים של האות a הוא זוגי, ואילו מספר המופעים של האות b ושל האות c הוא אי־זוגי.
האוטומט שבסעיף ב(2) — אוטומט סופי דטרמיניסטי שאינו מלא, מצבים q0–q10, q0 הוא המצב ההתחלתי:
- מעברים שסימן הקלט שלהם מופיע: q0→q1 (a), q1→q3 (b), q1→q2 (a), q2→q5 (b), q5→q7 (c).
- מעברים שסימן הקלט שלהם חסר: q2→q1; q3→q4 ו-q4→q3; q4→q8; q7→q8; q8→q9 ו-q9→q8; q5→q6 ו-q6→q5; q3→q10; q6→q10; לולאה עצמית על q10.
- אף מצב אינו מסומן כמצב מקבל.
לפניכם שלוש שפות מעל הא"ב {a , b}: L1 = { aⁿ bᵐ aᵏ | n, m, k > 0, n = k } L2 = { aⁿ bᵐ aᵏ | n, m, k > 0, n % 2 = k % 2 } L3 = { aⁿ bᵐ aᵏ | n, m, k > 0, n+m+k < 100 } לפניכם ארבעה סעיפים (1)–(4). ענו על כולם (בנימוק מספיק הסבר מילולי, אין צורך באוטומט).
בנוגע לכל אחת מן השפות L1 – L3 , כתבו אם היא רגולרית או לא רגולרית. נמקו את תשובתכם.
האם השפה L1 ∩ L3 רגולרית? נמקו את תשובתכם.
האם השפה L1 ∩ ‾L3 רגולרית? נמקו את תשובתכם.
האם השפה L2 ∩ ‾L3 רגולרית? נמקו את תשובתכם.
נתונה השפה L מעל הא"ב {a,b,c} : L = {aᵐ bᵏ cˣ | m, k, x > 0 וגם (m%2 = k%2 או m%2 = x%2)} הסבר: השפה L מכילה מילים שבהן כל אחת מן האותיות abc מופיעה פעם אחת לפחות, ולפי סדר זה (המופעים של a תחילה ואחר כך של b ואחר כך של c). כמו כן, אם מספר המופעים של האות a הוא זוגי/אי־זוגי, מספר המופעים של האות b או של האות c יהיה גם הוא זוגי/אי־זוגי בהתאמה. דוגמה למילה בשפה L היא abbbbccc , כי כל אחת מן האותיות abc מופיעה בה, ולפי הסדר הנדרש. כמו כן מספר המופעים של האות a הוא אי־זוגי, וכך גם מספר המופעים של האות c . דוגמה נוספת למילה בשפה L היא aaaabbc , כי כל אחת מן האותיות abc מופיעה בה, ולפי הסדר הנדרש. כמו כן מספר המופעים של האות a הוא זוגי, וכך גם מספר המופעים של האות b . דוגמה למילה שאינה בשפה L היא aabc . אומנם כל אחת מן האותיות abc מופיעה בה, ולפי הסדר הנדרש, אך מספר המופעים של האות a הוא זוגי, ואילו מספר המופעים של האות b ושל האות c הוא אי־זוגי.
לפניכם חמש מילים: abbcc , abcc , bbc , abc , abbac . העתיקו כל אחת מן המילים למחברתכם, וקבעו אם היא שייכת לשפה L או לא שייכת לשפה L . נמקו את קביעותיכם.
נתון לפניכם אוטומט סופי דטרמיניסטי שאינו מלא המקבל את השפה L . באוטומט קיימים כל המצבים וכל המעברים הנדרשים, אך בכמה מן המעברים חסרים סימני הקלט (התווים במעברים), והמצבים המקבלים באוטומט אינם מסומנים כלל. העתיקו את האוטומט למחברתכם, הוסיפו את סימני הקלט החסרים, וסמנו את המצבים המקבלים. הערה: האוטומט צריך להישאר סופי דטרמיניסטי שאינו מלא. אין להוסיף בו מצבים או מעברים, ואין לשנות את סימני הקלט המופיעים בו. תשובה שתהיה בה שינוי באוטומט הנתון לא תזוכה בנקודות. (האוטומט מתואר בתחילת השאלה.)
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.