שאלה 7 במסלול מודלים חישוביים. שני סעיפים בלתי-תלויים. בסעיף א׳ מוכיחים, בעזרת תכונות הסגירות של השפות הרגולריות, שהשפה L3={a^n b^m | n,m≥0, m%2≠n%2} רגולרית — מתוך L1={a^(2k)} ו-L2={b^(2k+1)}. בסעיף ב׳ נתונה שפה L של מילים מהצורה a^z·w1···wk·d^(k+1) (z אי-זוגי, wi∈{b^n c^m | n,m>0}), ויש למצוא את המילה הקצרה ביותר בה ולהשלים אוטומט מחסנית דטרמיניסטי חלקי (חסרים 3 מעברים) שמקבל אותה.
שאלה 7 במסלול מודלים חישוביים. שני סעיפים בלתי-תלויים. בסעיף א׳ מוכיחים, בעזרת תכונות הסגירות של השפות הרגולריות, שהשפה L3={a^n b^m | n,m≥0, m%2≠n%2} רגולרית — מתוך L1={a^(2k)} ו-L2={b^(2k+1)}. בסעיף ב׳ נתונה שפה L של מילים מהצורה a^z·w1···wk·d^(k+1) (z אי-זוגי, wi∈{b^n c^m | n,m>0}), ויש למצוא את המילה הקצרה ביותר בה ולהשלים אוטומט מחסנית דטרמיניסטי חלקי (חסרים 3 מעברים) שמקבל אותה.
אוטומט מחסנית דטרמיניסטי חלקי (חסר סימני מעבר על חלק מהקשתות) -- p-12.png / p12_diagram.png (300dpi)
states q0..q6, start q0, accepting q6 (double circle). Edges (as printed, some carry a transition label 'char/stack-top, ל"ש'=ללא שינוי i.e. no push/pop; some are drawn WITHOUT any label -- those are the 'missing transitions' the student must fill in): q0->q1 labeled 'a/⊢, ל"ש'; q1->q2 labeled 'a/⊢, ל"ש'; q1->q3 (label MISSING); q3->q4 (label MISSING); q4->q5 (label MISSING); q5->q6 labeled 'd/⊢, ל"ש'.
לפניכם השפות הרגולריות L1 ו-L2 מעל הא"ב {a,b}: L1={a^(2k) | k>=0}, L2={b^(2k+1) | k>=0}. הוכיחו בעזרת תכונות הסגירות של השפות הרגולריות שהשפה L3 רגולרית: L3={a^n b^m | n,m>=0, m%2 != n%2}.
נתונות השפות הבאות: L = {a^z w1 w2 ... wk d^(k+1) | z%2=1, wi∈L1, k>0}, L1={b^n c^m | n,m>0}. דוגמה למילה בשפה aaabbcbccddd: a^z=aaa, w1=bbc, wk=bcc, d^(k+1)=ddd (מספר תווי a הוא אי-זוגי; k=2 מילים מ-L1 בין ה-a-ים לד-ים, לכן d^(k+1)=d^3). (1) כתבו את המילה הקצרה ביותר בשפה L. (2) נתון אוטומט מחסנית דטרמיניסטי חלקי המקבל את השפה L. האוטומט כולל את כל המצבים (כולל סימון מצב מקבל). עליכם להשלים את המעברים החסרים ואת פירוט המעברים הקיימים (התו במעבר, הסימן בראש המחסנית והפעולה על המחסנית). הערה: אין להוסיף או להוריד מצבים מהאוטומט. העתיקו את אוטומט המחסנית למחברת הבחינה והשלימו אותו כך שיקבל את השפה L.
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.