0
Design a Turing Machine which accepts all strings of the form 0n1n, n>=1

Mumbai university > Comp > SEM 4 > TCS

Marks: 10M

Year: Dec 2014

0
0
  • 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 enter image description here enter image description here

0
Please log in to add an answer.

Continue reading

Find answer to specific questions by searching them here. It's the best way to discover useful content.

Find more