Question

(a) Design a Turing machine to accept all
sets of palindromes over {0,1}*. Also
write the instantaneous description on
the string 1001001.​

Answer 1

Answer:

Explanation:

Turing Machine was invented by Alan Turing in 1936 and it is used to accept Recursive Enumerable Languages (generated by Type-0 Grammar).

A turing machine consists of a tape of infinite length on which read and writes operation can be performed. The tape consists of infinite cells on which each cell either contains input symbol or

a special symbol called blank. It also consists of a head pointer which points to cell currently being read and it can move in both directions. A TM is expressed as a 7-tuple (Q, T, B, ∑, δ, q0, F) where:

Q is a finite set of states

T is the tape alphabet (symbols which can be written on Tape)

B is blank symbol (every cell is filled with B except input alphabet initially)

∑ is the input alphabet (symbols which are part of input alphabet)

δ is a transition function which maps Q × T → Q × T × {L,R}. Depending on its present state and present tape alphabet (pointed by head pointer), it will move to new state, change the tape symbol (may or may not) and move head pointer to either left or right.

q0 is the initial state

F is the set of final states. If any state of F is reached, input string is accepted.Let us construct a turing machine for L={0n1n|n>=1}

Answer 2

Answer:

Turing machine to accept all sets of palindromes over {0,1}

Explanation:

• The turning machine was invented by Alan turning in the year 1936. It is used for the purpose of accepting the Recursive Enumerable Languages.

Representation of the turning machine:

• The turning machine consists of tape of length which is infinite and it will reach and write the operations which can be performed.
• The tape consists of cells that are infinite and teach cells will contain an input symbol called as blank.
• It has a head pointer that will point towards the cell that is being read currently and it can be seen to move towards both directions.

Given that:

Turing machine to accept all sets of palindromes over {0,1}.

Solution:

Let us consider that,

A Turing machine (TM) is a 7-tuple (Q, ∑, Γ, δ, q0, q accept , qreject).

Where,

Q is a finite set of states.

∑ is the known as input alphabet that does not contain the blank symbol t.

Γ  is the known as tape alphabet, where t ∈ Γ and ∑ ⊆ Γ.

δ: (Q × Γ) → (Q × Γ × {L, R}) is the transition function.

q0 ∈ Q is the start state.

qaccept ∈ Q is the called accept state.

qreject ∈ Q is the called reject state,

where qreject ≠ qaccept.

#SPJ2