Theory of Computation — Winter 2020

Discuss Recursive definition. Also define the language Ldefined by the following recursive definition over ∑ = {a, b}: ^ ∈ L; For every x ∈ L, xa, bx, and abx are in L; Nothing else is in L.

Let relation R = {(a,b) : a + b = 10 and a, b ∈ N}. Decide whether Ris an equivalence relation or not. Justify your answer with proper reason.

Using the principle of mathematical induction, for all n > 0, prove that, n (n+1) (4n−1) 1×2+3 ×4+5 ×6 + .....+ (2n−1) ×2n =3

Write regular expressions for the following languages defined over ∑ = {0, 1}:

The language of all the strings that do not end with 01. (ii) The language of all the strings containing even number of 0’s and even number of 1’s.

Draw DFA for the following languages defined over ∑ = {a, b}:

The language of all the strings with next-to-last symbol is a. (ii) The language of all the strings containing substring bba.

Convert the following NFA into its equivalent DFA using the subset construction.

Prove that the context-free languages are closed under union.

For the following CFG, find out two left most derivations for the string “aaabb” and also draw the corresponding parse trees. S → XY X → XX | a Y → YY | b

Define CNF. Also convert the following CFG into its equivalent CNF. S → aX | Y | bab X → ^ | Y Y → bb | bXb

What language over {a, b}* does the CFG with productions S → aT | bT T → aS | bS | ^ generate? Prove your answer.1

Let Mand Mbe the FAs pictured in Fig. (i) and Fig. (ii) accept the languages12 Land L , respectively.12 Fig. (i) Fig. (ii) Draw FAs accepting the following languages:

L ∪L12 (ii) L′2

Find context-free grammar generating the languages below.

{aibjck | j = i or j = k} (ii) {aibjck | j ≠ i + k}

Define - A Pushdown Automaton and acceptance by a PDA.

Convert the CFG with following productions into its equivalent PDA. S → [S] | SS | ^

Design a PDA to accept L = {wcwR | w ∈ (a,b)*}.

Discuss pumping lemma for context free languages.

Define bijection. Decide and justify whether the function f : N → Ndefined by f(n) = n2 is bijection or not.

Design a PDA to accept L = {xcy | x, y∈ (a,b)* and |x| = |y|}.

Discuss - recursively enumerable languages.

Discuss - universal Turing machine.

Draw Turing machine for L = {xx | x ∈ {a, b}*}. Also trace out the same on input string aba.

Discuss chomsky hierarchy.

Discuss primitive recursive function using proper example.

Draw Turing machine to accept language L = {x ∈ {a, b}* | x ends with aba}. Also trace out the same on input string aba.