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

Mumbai university > Comp > SEM 4 > TCS

Marks: 10M

Year: Dec 2014

ADD COMMENTlink
modified 3.4 years ago  • written 3.4 years ago by gravatar for Pooja Joshi Pooja Joshi750
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

ADD COMMENTlink
written 3.4 years ago by gravatar for Pooja Joshi Pooja Joshi750
Please log in to add an answer.