טוען...
טוען...
לפניכם מכונת טיורינג המקבלת מילים מעל הא״ב {a, b} (מקרא: R – ימין, L – שמאל).
בסעיף א שלפניכם תתבקשו לבצע מעקב אחר פעולת המכונה. במעקב יש להראות בכל שלב את הסרט, מעל איזה תא ממוקם הראש הקורא, ובאיזה מצב q0–q5 נמצאים.
להלן דוגמה לאופן שבו יש לבצע מעקב בעבור המכונה הנתונה והמילה bb.
| שלב | הסרט | הראש הקורא מעל | מצב |
|---|---|---|---|
0 | ⊢ b b Δ Δ … | תא 1 (b) | q0 |
1 | ⊢ b b Δ Δ … | תא 2 (b) | q0 |
2 | ⊢ b b Δ Δ … | תא 3 (Δ) | q0 |
3 | ⊢ b b Δ Δ … | תא 2 (b) | q5 |
(1) עקבו אחרי פעולת המכונה בעבור המילה a. יש להציג את המעקב.
(2) עקבו אחרי פעולת המכונה בעבור המילה aba. יש להציג את המעקב.
(3) הציגו את הסרט המתקבל בגמר הפעולה בעבור המילה baba. אין צורך להציג את המעקב.
(1) האם קיימת מילה המכילה גם את a וגם את b שאינה משתנה לאחר הרצת המכונה עליה? אם כן – כתבו דוגמה למילה כזו. אם לא – נמקו את תשובתכם.
(2) כתבו בקצרה מה המכונה עושה.
לפניכם מכונת טיורינג המקבלת מילים מעל הא״ב {a, b} (מקרא: R – ימין, L – שמאל).
בסעיף א שלפניכם תתבקשו לבצע מעקב אחר פעולת המכונה. במעקב יש להראות בכל שלב את הסרט, מעל איזה תא ממוקם הראש הקורא, ובאיזה מצב q0–q5 נמצאים.
להלן דוגמה לאופן שבו יש לבצע מעקב בעבור המכונה הנתונה והמילה bb.
| שלב | הסרט | הראש הקורא מעל | מצב |
|---|---|---|---|
0 | ⊢ b b Δ Δ … | תא 1 (b) | q0 |
1 | ⊢ b b Δ Δ … | תא 2 (b) | q0 |
2 | ⊢ b b Δ Δ … | תא 3 (Δ) | q0 |
3 | ⊢ b b Δ Δ … | תא 2 (b) | q5 |
(1) עקבו אחרי פעולת המכונה בעבור המילה a. יש להציג את המעקב.
(2) עקבו אחרי פעולת המכונה בעבור המילה aba. יש להציג את המעקב.
(3) הציגו את הסרט המתקבל בגמר הפעולה בעבור המילה baba. אין צורך להציג את המעקב.
(1) האם קיימת מילה המכילה גם את a וגם את b שאינה משתנה לאחר הרצת המכונה עליה? אם כן – כתבו דוגמה למילה כזו. אם לא – נמקו את תשובתכם.
(2) כתבו בקצרה מה המכונה עושה.