Prove the theorem If L is a finite language, then L can be defined by a regular expression.

For the NDFA shown, check whether the input string 0100 is accepted or not.

<img src='./qimages/11463-1b.jpg'>

Construct CFG for the given set 1 m n}.

Discuss about PDA acceptance:

From empty stack to final state

From final state to empty stack

Is it possible that a Turing Machine could be considered as a computer of functions from integers to integers? If yes, justify your answer.

Show that 3n 2

Show that 3n 2

Construct a NFA transition diagram and

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

Prove that if L and M are regular languages, then L n M is also a regular language.

Given a CFG G with N T and

<img src='./qimages/11463-3a.jpg'>

Obtain the derivation tree and language generated

Check whether the language given by L b^m c^n a CFL or not.

Explain the following with examples:

Multi-Tape Turing Machine

K-dimensional Turing Machine

Show that the function x^2 is primitive recursive.

Explain any two undecidable problems with respect to Turing Machine.

Show that the vertex cover problem is NP-complete.