MyQuestionIcon

1

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

Construction of Turing Machines Part - 2

Consider the ...

Question

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

Open in App

Solution

The Turing Machine T accepts the regular language corresponding to the regular expression aa* + bb*, Hence the correct choice is option (d).

Suggest Corrections

thumbs-up

0

Similar questions

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

Q. Consider the state diagram of Turing Machine T, over

\sum = {a} and Γ = {a, □} .

The language accepted by T will be

Q. Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M.
Which of the following decision problems are undecidable?
I. Given a regular expression R and a string w,is

ω ε

L(R)?
II. Given a context-free grammar G, is L(G)=

ϕ

III. Given a context-free grammar G, is L(G) =

\sum^{*}

for some alphabet

\sum

?
IV. Given a Turing machine M and a string

ω

ω ε

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:

Consider < M > be the encoding of a Turing Machine as a string over alphabet \sum = {0, 1} . Consider L = {< M > | M is TM which halts on all the input and L(M) =L' for some undecidable language L^{'}} .

View More

Join BYJU'S Learning Program

similar_icon

Related Videos

lock

Construction of Turing Machines Part - 2

OTHER

Watch in App

explore_more_icon

Explore more

Construction of Turing Machines Part - 2

Join BYJU'S Learning Program

CrossIcon