Given the Turing machine 𝑀 = (𝑄, Σ, Γ, 𝛿, 𝑞0, 𝐵, 𝐹) with 𝑄 = {&#
Posted: Fri Jun 10, 2022 11:56 am
Given the Turing machine 𝑀 = (𝑄, Σ, Γ, 𝛿, 𝑞0, 𝐵, 𝐹) with 𝑄 =
{𝑞0, ..., 𝑞4}, Σ = {0, 1}, Γ = {0, 1, 𝑋, 𝑌, 𝐵}, and 𝐹 = {𝑞4}.
The transition function 𝛿 is given by:
a) Determine the configuration sequence that 𝑀 runs through when
𝑥 = 001101 is entered.
b) Does 𝑀 accept the input 𝑥?
c) Which language 𝐿𝑀 does 𝑀 accept?
(d) Use 𝛿 to construct a transition function 𝛿′ such that 𝑀′ = (𝑄,
Σ, Γ, 𝛿′, 𝑞0, 𝐵, 𝐹) the language 𝐿𝑀′ = 𝐿𝑀 ⋅
{1𝑛 ∣ 𝑛 ∈ ℕ0} accepted.
90 91 92 93 94 0 (91, X, R) (91,0, R) (92,0, L) 1 (92, Y, L) X (90, X, R) Y (93, Y, R) (91,Y, R) (92, Y,L) (93, Y, R) B (94, B, R)
{𝑞0, ..., 𝑞4}, Σ = {0, 1}, Γ = {0, 1, 𝑋, 𝑌, 𝐵}, and 𝐹 = {𝑞4}.
The transition function 𝛿 is given by:
- 1 (19.5 KiB) Viewed 98 times
𝑥 = 001101 is entered.
b) Does 𝑀 accept the input 𝑥?
c) Which language 𝐿𝑀 does 𝑀 accept?
(d) Use 𝛿 to construct a transition function 𝛿′ such that 𝑀′ = (𝑄,
Σ, Γ, 𝛿′, 𝑞0, 𝐵, 𝐹) the language 𝐿𝑀′ = 𝐿𝑀 ⋅
{1𝑛 ∣ 𝑛 ∈ ℕ0} accepted.
90 91 92 93 94 0 (91, X, R) (91,0, R) (92,0, L) 1 (92, Y, L) X (90, X, R) Y (93, Y, R) (91,Y, R) (92, Y,L) (93, Y, R) B (94, B, R)