Differentiate Kleen closure from positive closure. Compute positive and Kleen closure of {ab}. [5]

Define CFG. Construct a CFG that generates the language of all palindromes over {a,b} that do not contain the substring aa. Show the leftmost derivation and construct the equivalent parse tree for string babbbab. [10]

Prove that th language is not a context free grammar. [5]

How is conversion of PDA to CFG done? Illustrate with example. [5]

Describe the extended transition function of NFA. Construct a NFA, using transition table and transition diagram, over {0, 1} that accept the string having substring 01 and ends with 1. Show the acceptance of 0111. [10]

Design a Mealy machine over {a, b} that generates output 'A' if the input string ends with aa else output 'B' if the string ends with bb. [5]

Construct a PDA that accepts string over $\Sigma = \{ a, b \}$ that contains equal number of a's followed by equal number of b's. Show acceptance of aabb and aab. [5]

Construct regular expression over {1,2,...,9} that represents a. strings of even numbers with length 4 starting with 2 and ending with 8. b. strings starting with odd numbers and ending with even numbers. [5]

State Arden's theorem. Convert following DFA into its regular expression using Arden theorem. [5]

How Turing Machine is used as a computing function? Construct a TM for simulating a function f(x) = 2x for x = {1}. Iterate the TM for input 11 and generate the output 1111. [10]

Describe how multi-stack TM is different from the semi-infinite tape TM? [5]

What is intractability? Define time and space complexity of turing machine. [5]