סעיף א - שפות פורמליות מעל הא"ב {a, b, c}:
סעיף א - שפות פורמליות מעל הא"ב {a, b, c}:
L1 = { a^n b^k c^n | 0 < n < 1000 < k } L2 = { a^n b^k c^n | 0 < k < 1000 < n } L3 = { a^n b^k c^n | 0 < k < 1000 < n < 2000 }
L4 = L2 ∩ R(L2) (R(L) = ההפכית של L - כל מילה כתובה מהסוף להתחלה)
L5 = L1 ∪ L2
L6 = ¬L1 ∪ ¬L3 (¬L = המשלים של L ביחס ל-Σ*, כאשר Σ = {a, b, c})
בנוגע לכל אחת מן השפות יש לכתוב אם היא רגולרית או לא, ולנמק. די בהסבר מילולי - אין צורך לבנות אוטומט.
סעיף ב - השפה L מעל הא"ב {a, b, c}:
L = { a^n b^m a^k w | n, m, k > 0 }
w היא מילה מעל {b, c} שנקבעת כך:
אם n+k מתחלק ב-3 בלי שארית - w היא המילה הריקה.
אם n+k מתחלק ב-3 עם שארית 1 - w אינה מכילה כלל את האות b (כלומר w מורכבת רק מ-c-ים).
אם n+k מתחלק ב-3 עם שארית 2 - w אינה מכילה כלל את האות c (כלומר w מורכבת רק מ-b-ים).
דוגמה למילה בשפה: a b b a a a c c c (n=1, m=2, k=3, w=ccc; n+k=4 נותן שארית 1, ולכן w בלי b).
יש לבנות אוטומט סופי דטרמיניסטי שאינו מלא המקבל את L.
לפניכם שלוש שפות מעל הא"ב {a,b,c}: L1={a^n b^k c^n | 0<n<1000<k}. L2={a^n b^k c^n | 0<k<1000<n}. L3={a^n b^k c^n | 0<k<1000<n<2000}. בנוגע לכל אחת מן השפות L3-L1, כתבו אם היא רגולרית או לא. נמקו את תשובתכם (די בהסבר מילולי; אין צורך באוטומט).
לפניכם שלוש שפות מעל הא"ב {a,b,c}: L4 = L2 ∩ R(L2). L5 = L1 ∪ L2. L6 = complement(L1) ∪ complement(L3). בנוגע לכל אחת מן השפות L6-L4, כתבו אם היא רגולרית או לא. נמקו את תשובתכם (די בהסבר מילולי; אין צורך באוטומט).
לפניכם השפה L מעל הא"ב {a,b,c}: L = {a^n b^m a^k w | n,m,k > 0}. w היא מילה מעל {b,c} המאופיינת באופן שלהלן: אם n+k מתחלק ב-3 בלי שארית, w היא מילה ריקה. אם n+k מתחלק ב-3 עם שארית 1, w היא מילה שאינה מכילה שום כלל את האות b. אם n+k מתחלק ב-3 עם שארית 2, w היא מילה שאינה מכילה שום כלל את האות c. דוגמה למילה השייכת לשפה L: a b b a a a c c c (n=1,m=2,k=3, w). הסבר: n=1,k=3, n+k=4 מתחלק ב-3 עם שארית 1, ו-w היא מילה שאינה מכילה כלל את האות b. בנו אוטומט סופי דטרמיניסטי שאינו מלא המקבל את השפה L.
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.