0
3.0kviews
Design a turing machine to accept the language 0^n 1^n 2^n

Mumbai University > Computer Engineering > Sem 4 > Theoretical Computer Science

Marks: 10M

Year: Dec 2016

1 Answer
0
150views

A Turing Machine is a 6-tuple

  • M = (Q, ∑, I, q0, δ, F) where

    1. Q - finite, non-empty set of states

    2. ∑ - finite set of at least 2 symbols: the alphabet. ^ ∈ ∑

    3. I - non-empty subset of ∑; ^ ∉ I; input alphabet

    4. q0 - q0 ∈ Q; starting or initial state

    5. d - δ: (Q\F) x ∑ ⇒Q x ∑ x {-1, 0, 1}, a partial function, the instruction table

    6. F - F ⊆ Q, the set of final or halting states

enter image description here

q0-0 make it X

q1-1 make it y

q2-2 make it z

q3-comeback

q4-check

qf-final state

Please log in to add an answer.