PHP Search Engine

Apr 22 In-Class Exercise Thread .

Post your solutions to the Apr 22 In-Class Exercise to this thread.

Best,

Chris

Post your solutions to the Apr 22 In-Class Exercise to this thread. Best, Chris

-- Apr 22 In-Class Exercise Thread

(Edited: 2020-04-22)

((resource:4.PNG|Resource Description for 4.PNG))

-- Apr 22 In-Class Exercise Thread

Let the NTM M = {Q, S, T, delta, q_0, F}, where

Q = {q_0, q_1}, S = {a,b}, T = {a,b,_}, F = {q_1}, and delta = {δ(q_0,a)={(q_0,a,L),(q_0,a,R)}, δ(q_0,b)={(q_0,a,L),(q_1,b,L)}.

Let NTM read the string "b".

Then, M makes the following transition, which is in the transition function: (q_0, b) (q_1, b, L).

And, q_1 is an accept state in F, so we're done.

(Edited: 2020-04-22)

1. Let the NTM M = {Q, S, T, delta, q_0, F}, where Q = {q_0, q_1}, S = {a,b}, T = {a,b,_}, F = {q_1}, and delta = {δ(q_0,a)={(q_0,a,L),(q_0,a,R)}, δ(q_0,b)={(q_0,a,L),(q_1,b,L)}. 2. Let NTM read the string "b". Then, M makes the following transition, which is in the transition function: (q_0, b) ⊢ (q_1, b, L). And, q_1 is an accept state in F, so we're done.

-- Apr 22 In-Class Exercise Thread

(Edited: 2020-04-22)

((resource:Capture.PNG|Resource Description for Capture.PNG))

-- Apr 22 In-Class Exercise Thread

(Q,Σ,Γ,δ,1,H)

where Q={1, 2}

Σ = {a}

Γ = {a, }

δ = { (1, a) -> (1, a, R)

  (1, a) -> (2, □, R)

}

H = {2}

for input aa

(1, |a|a) |- (1,a|a|) |- (2, a)

where for wx|y|z, symbol y is being read in wxyz

(Q,Σ,Γ,δ,1,H) where Q={1, 2} Σ = {a} Γ = {a, □} δ = { (1, a) -> (1, a, R) (1, a) -> (2, □, R) } H = {2} for input aa (1, |a|a) |- (1,a|a|) |- (2, a□) where for wx|y|z, symbol y is being read in wxyz

-- Apr 22 In-Class Exercise Thread

N = ({q,q}, {a}, {a,_}, δ, q, {q}) δ = {(q,a) -> (q,a,R) (q,a) -> (q,,R)} Input: aaa (q, [a]aa) |- (q, a[a]a) |- (q, aa[a]) |- (q`, aa)

(Edited: 2020-04-22)

N = ({q,q@BT@}, {a}, {a,_}, δ, q, {q@BT@}) δ = {(q,a) -> (q@BT@,a,R) (q,a) -> (q@BT@,_,R)} Input: aaa (q, [a]aa) |- (q, a[a]a) |- (q, aa[a]) |- (q@BT@, aa_)

-- Apr 22 In-Class Exercise Thread

M = {Q, Σ, Γ, δ, q, H} Q = {0, 1} Σ = {x} Γ = {x, } δ = {(0, x) -> (0, x, R) (0, x) -> (1, , R)} H = {1}

input xx (0, (, x, x) |- (x, x, )) |- (1, (x, , ))

M = {Q, Σ, Γ, δ, q, H} Q = {0, 1} Σ = {x} Γ = {x, □} δ = {(0, x) -> (0, x, R) (0, x) -> (1, □, R)} H = {1} input xx (0, (□, x, x□) |- (□x, x, □)) |- (1, (□x□, □, □))

-- Apr 22 In-Class Exercise Thread

((resource:Screen Shot 2020-04-22 at 9.54.45 PM.png|Resource Description for Screen Shot 2020-04-22 at 9.54.45 PM.png))

-- Apr 22 In-Class Exercise Thread

((resource:422inclass.jpg|Resource Description for 422inclass.jpg))

-- Apr 22 In-Class Exercise Thread

((resource:IMG_3029.jpg|Resource Description for IMG_3029.jpg))