נתונה מכונת טיורינג המקבלת מילים מעל הא"ב {a, b}. מקרא: R - ימין, L - שמאל, Δ - תא ריק.
נתונה מכונת טיורינג המקבלת מילים מעל הא"ב {a, b}. מקרא: R - ימין, L - שמאל, Δ - תא ריק.
תא 0 של הסרט מכיל את סימן תחילת הסרט (⊢), המילה כתובה מתא 1 ואילך, והראש הקורא מתחיל בתא 1 במצב q0. המצב המקבל הוא q5 (מסומן בתרשים בעיגול כפול).
טבלת המעברים (בכל שורה: קורא / כותב , כיוון):
| ממצב | האות הנקראת | כותב | כיוון | למצב |
|---|---|---|---|---|
| q0 | b | b | R | q0 |
| q0 | a | Δ | R | q1 |
| q0 | Δ | Δ | L | q5 |
| q1 | a | Δ | L | q2 |
| q1 | b | Δ | L | q3 |
| q1 | Δ | Δ | R | q5 |
| q2 | Δ | a | R | q4 |
| q3 | Δ | b | R | q4 |
| q4 | Δ | Δ | R | q1 |
דוגמת המעקב שהשאלון מדפיס, בעבור המילה bb (הסרט: ⊢ b b Δ Δ ...):
| שלב | מצב | תא הראש |
|---|---|---|
| 0 | q0 | 1 |
| 1 | q0 | 2 |
| 2 | q0 | 3 |
| 3 | q5 | 2 |
הסרט אינו משתנה כלל במעקב הזה.
מכונת טיורינג בעלת 6 מצבים (q0-q5), q5 מצב מקבל (עיגול כפול). מעברים: q0 self-loop b/b,R; q0->q1 a/Δ,R; q1->q5 Δ/Δ,R; q1->q3 b/Δ,L; q1<->q4 Δ/Δ,R (מ-q4 ל-q1); q5->q1 Δ/Δ,L (חזרה); q3->q4 Δ/b,R; q4->q2 Δ/a,R; q2->q1 a/Δ,L.
q0 --b/b,R(loop)--> q0
q0 --a/Δ,R--> q1
q1 --Δ/Δ,R--> q5 (accept)
q5 --Δ/Δ,L--> q1
q1 --b/Δ,L--> q3
q3 --Δ/b,R--> q4
q4 --Δ/Δ,R--> q1
q4 --Δ/a,R--> q2
q2 --a/Δ,L--> q1
[תיקון קריאה 04.09: אין קשת q5→q1; הקשת Δ/Δ,L היא q0→q5 (q5 = מצב סופי) — ראו tm_q9.py]
דוגמת מעקב עבור המילה bb: 4 שלבים (0-3) עם מצב הראש הקורא (q0,q0,q0,q5) על תאים 0,1,2,2 של הסרט [⊢ b b Δ Δ ...].
step0: q0 at cell0: |⊢|b|b|Δ|Δ|...
step1: q0 at cell1: |⊢|b|b|Δ|Δ|...
step2: q0 at cell2: |⊢|b|b|Δ|Δ|...
step3: q5 at cell2: |⊢|b|b|Δ|Δ|...
[תיקון קריאה 04.09: אין קשת q5→q1; הקשת Δ/Δ,L היא q0→q5 (q5 = מצב סופי) — ראו tm_q9.py]
עקבו אחרי פעולת המכונה בעבור המילה a. יש להציג את המעקב.
עקבו אחרי פעולת המכונה בעבור המילה aba. יש להציג את המעקב.
הציגו את הסרט המתקבל בגמר הפעולה בעבור המילה baba. אין צורך להציג את המעקב.
האם קיימת מילה המכילה גם את a וגם את b שאינה משתנה לאחר הרצת המכונה עליה? אם כן - כתבו דוגמה למילה כזו. אם לא - נמקו את תשובתכם.
כתבו בקצרה מה המכונה עושה.
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.