Theory of Computation — Winter 2019

Define – bijection function. Check whether the function f ∶ Z → Zdefined by f(x) = 2x is a bijection function or not. Justify your answer.

Draw an FA that recognizes the language of all strings containing even no of 0’s and even no of 1’s over ∑ = {0,1}. Also write a regular expression for the same language.

Write the principle of Mathematical Induction. Prove using mathematical induction that for every n ≥ 0, n 1 n ∑ = i (i+1) n+1 i=1 (Consider the sum on the left is 0 for n = 0)

Find regular expression and also derive the words corresponding to the language defined recursively below over ∑ = {a,b} . i. a ∈ L ii. For any x ∈ L,xa and xb are elements of L

Define – Equivalence relation. Arelation on the set {1,2,3} is given as R = {(a,b) | a−b is an even no}. Check whether Ris equivalence relation or not. Give reasons.

Give transition table for PDA recognizing the following language and trace the move of the machine for input string abcba: L = {xcxr | x ∈ {a,b}∗}

Give transition table for PDA accepting the language of all odd-length strings over {a, b} with middle symbol a. Also draw a PDA for the same.

Let FA and FA be the FAs as shown in the figure recognizing the languages Land Lrespectively. Draw an FA recognizing the language, L U L . FA :1 FA :2

Define – Moore machine. Convert the following Moore machine into its equivalent Mealy machine: After input a After input b Old state Output New state New state −q q q q q q 1132 q q q 0223 q q q 1333

Convert the following NFA - Ʌ into its equivalent DFA that accepts the same language:

Prove that – “If there is a CFG for the language Lthat has no Ʌ-productions, then there is a CFG for Lwith no Ʌ-productions and no unit productions”. Support your answer with the help of the following CFG: S → A | bb A → B | b B → S | a

Write CFG for the following languages : i. {aibjck | i = j+k} ii. {aibjck | j = i or j = k}

Define – ambiguous grammar, leftmost derivation. Check whether the following grammars are ambiguous or not. Justify your answer with proper reason. i. S → ABA ii. S → A | B A → aA | Ʌ A → aAb | aabb B → bB | Ʌ B → abB | Ʌ

Describe the language generated by the following grammars: i. S → aA | bC | b ii. S → aT | bT | Ʌ A → aS | bB T → aS | bS B → aC | bA | a C → aB | bS

Discuss – Nondeterministic Turing Machines and Universal Turing Machines2

Find a minimum-state FA for the following FA that recognizes the same language using the minimization algorithm:

Find the CFG for the regular expression : (011+1)∗ (01)∗

Prove that the language L = {anbnabn+1 | n = 1,2,3,…} is nonregular using pumping lemma.

Convert the following CFG into its equivalent CNF: S → TU | V T → aTb | Ʌ U → cU | Ʌ V → aVc | W W → bW | Ʌ

Convert the following CFG into its equivalent PDA. S → AB A → BB B → AB A → a B → a | b

Show using the pumping lemma that the following language is not a CFL. L = {aibjck | i < j < k}

Draw a Turing Machine that accepts the language {anbnan | n ≥ 0} over {a,b}∗. Also trace the TM on input string aaabbbaaa.

Define Context Sensitive Language and Context Sensitive Grammar. Write CSG for L = {an bn cn| n ≥ 1}.

Define - Primitive recursive functions and also give complete primitive recursive derivations for the function, f ∶ N → Ndefined by Add(x,y) = x+y.

Draw a Turing Machine that accepts the language {xx | x ∈ {a,b}∗}. Also trace the TM on input string aa.