MyQuestionIcon

1

You visited us 1 times! Enjoying our articles? Unlock Full Access!

A Turing mach...

Question

A Turing machine is expressed as a 7-tuple $(Q, \sum Γ, δ, q_{0}, B, F) where Γ$ is complete set of tape symbols and $\sum$ is finite set of input symbols then what is always true?

Open in App

Solution

$\sum \subseteq Γ - (Blank symbol)$

Suggest Corrections

thumbs-up

0

Similar questions

Q. Let A and B be finte alphabets and let # be a symbol outside both A and B. Let f be a total function from A* to B*. We say f is computable if there exists a Turing machine M which given an input x in A*, always halts with f(x) on its tape. Let

L_{1}

denote the language {x # f(x) | x

ϵ

A*}. Which of the following statements is true:

Q. A single tape Turning Machine M has two states q₀ and q₁, of which q₀ is the starting state. The tape alphabet of M is {0, 1, B} and its input alphabet is {0, 1}. The symbol B is the blank symbol used to indicate end of an input string The transition function of M is described in the following table:

	0	1	B
q₀	q₁, 1, R	q₁,1, R	Halt
q₁	q₁,1, R	q₀, 1, L	q₀, B, L

The table is interpreted as illustrated below. The entry (q₁, 1 , R) in row q₀ and column 1 signifies that if M is in state q₀ and reads 1 on the current tape square, then it writes 1 on the same tape square, moves its tape head one position to the right and transitions to state q₁. Which of the following statements is true about M?

Q. Consider the following Turing Machine T over the alphabet {a,b} and tape alphabet {a, b, t}. Here 't' represent tape alphabate.

The language accepted by the above Turing Machine T will be

Q. A canonical set of items is given below:

S \to L \cdot > R

Q \to R \cdot

On input symbol > the set has

Q. Consider the following Turing Machine M over the alphabet {a, b} and tape alphabet

{a, b, □}

The language accepted by the above M is

View More

Join BYJU'S Learning Program

similar_icon

Related Videos

lock

States of Matter

Watch in App

Join BYJU'S Learning Program

CrossIcon