Define the extended transition function of DFA. Draw a DFA accepting language L = {1ⁿ | n = 2, 3, 4…. }. Show acceptance of strings 1110011 and 1110 using extended transition function.

What is deterministic pushdown automaton? Configure a pushdown automaton accepting the language, L={w C w^R | w ∈ (0,1)^*}. Show instantaneous description of strings 011C110 and 10C10.

How a Turing Machine works?  Construct a Turing machine accepting the language L = {(ⁿ)ⁿ}. Also show the transition diagram of the machine. Illustrate whether a string (()) is accepted by the Turing machine or not.

When a grammar is said to be in CNF? Convert the following grammar to CNF:

S → 1A | 0B | ε

A → 1AA | 0S | 0

B → 0BB | 1 | A

C → CA | CS

Define epsilon NFA. Configure equivalent epsilon NFA for the regular expression (ab U a)^*.

Differentiate Kleene closure from positive closure. For ∑ = {0,1}, compute ∑^* and ∑².

Write the regular expression over {0,1} for strings

• Not ending with 0
• Of length at least 3 that ends with 00.

What is undecidable problem? Define post’s correspondence problem with an example.

How pumping lemma can be used to prove that any language is not a regular language? Show that language, L = {0ⁿ1ⁿ | n>0} is not a regular language.

Discuss how Turing Machine with multiple tracks differs from a Turing Machine with multiple tapes.

How context free grammars are defined? Write a context free grammar over {0,1}, where the strings start and end with the same symbol.

What is halting problem? How can you argue that halting problem is undecidable?