Give the regular expression for the strings a^7 ...}.

List three applications of regular expressions.

Describe briefly the Deterministic Turing Machine.

Tabulate the Chomsky hierarchy of grammar with an example.

Convert the following regular expression into an FA:


Using parse tree, verify whether the given grammar is ambiguous or not.

aSb X
a

Show that if L is a regular language, then L is also regular.

Derive the equivalent FA from the following NFA

<img src='./qimages/14197-2a.jpg'>

Convert the following regular expression into an FA: ab*

Give a regular expression for all strings that have no two consecutive a's.

Show that the language L a^n b n 0 is not regular.

Design a Turing Machine which accepts all the strings of the language

Explain the Non-Deterministic Turing Machine, with an example.

Construct a PDA to accept L C w^R w € where w^R means Reversed w.

Show that the language L b^n a^n n is not context free.

Show that the following function
n
0 else
is primitive recursive.

Show that the blank tape halting problem is undecidable.

If 3x^2 then show that x^3 and also x^4

Show that the Travelling Salesman problem is NP complete.