Define deterministic finite automation. Construct a non-deterministic finite automata (NDFA) accepting ba}.

Differentiate between Mealy Machine and Moore Machine.

Construct a finite automation equivalent to the regular expression 1(1 00).

Find a reduced grammar equivalent to the grammar S aAa, A bBB, B ab, C aB.

3. Write the regular expression for the following language:

The set of all strings, of and which ends with 1 and does not contain substring 00.

The set of all strings of and with an equal number of and such that no prefix has two more than nor more than 0's.

4. Define a deterministic push down automata (DPDA). Give an example of a context free language that is not accepted by any DPDA.

5. Define Turing Machine. Design a Turing Machine that computes the integer function f defined as follows:

3^N where N is Integer and N 0.

6. Prove that if a language L and complement of L both are recursively enumerable, then L is recursive.

7. Design a Mealy Machine that accepts binary string divisible by 3.

8. Discuss NP-complete and NP-hard problems with proper examples.

9. Non-deterministic PDA is not equivalent to deterministic PDA In terms of language recognition. Explain.

10. Write short notes on any two of the following:

Halting Problem

Myhill-Nerode Theorem

Universal Turing Machine