Define Chomsky Normal Form and Greibach Normal Form in reference to CFG. Give a suitable example of each. [5]

Give the formal definition of DFA. Construct a DFA accepting all strings of {0, 1} with even number of 0's and even number of 1's. [5]

Construct a NFA accepting language of {0, 1} with each string ending with 01 and convert it into equivalent DFA. [5]

How can you define the language accepted by a PDA? Explain how a PDA accepting language by empty stack is converted into an equivalent PDA accepting by final state and vice-versa. [10]

Construct a PDA accepting language over {0, 1} representing strings with equal no of 0s and 1s. Show by sequence of IDs that 0101 is accepted by this PDA. [5]

Define the NFA with $\epsilon-transition$ and $\epsilon-closure$ of a state. Show that for every regular expression r, representing a language L, there is $\epsilon-NFA$ accepting the same language. Also convert regular expression (a+b)*ab* into equivalent Finite Automata. [10]

Give the regular expressions for following language over alphabet {0, 1}. a. Set of all strings with 2nd symbol from right is 1. b. Set of all strings starting with 00 or 11 and ending with 10 or 01. [5]

Show that language is not a regular language. [5]

Define a Turing machine. Construct a TM that accept $L = \{ wcw^R \mid w \in \{0, 1\} \text{ and } c \text{ is } \varepsilon \text{ or } 0 \text{ or } 1 \}$. Show that string 0110 is accepted by this TM with sequence of Instantaneous Description (ID). [10]

Describe the Turing machines with multiple tape, multiple track and storage in state. [5]

Define complexity of a Turing machine. Explain about big Oh, big Omega and big Theta notation used for complexity measurement. [5]

What do you mean by tractable and Intractable problems? Explain with reference to TM. [5]