Theory of Computation — Summer 2023

Define one-to-one function and also give its example. Decide and justify whether the function f : N → Ndefined by f (x) = min(x, 2) is one-to-one or not.

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

L ⋂ L12 (ii) L′1

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

Each case below gives a recursive definition of a subset Lof {a, b}*. Give a simple nonrecursive definition of Lin each case.

a ∈ L; for any x ∈ L, xa and xb are in L. (ii) a ∈ L; for any x ∈ L, xb, ax, and bx are in L.

Write CFG for generating each of the following languages:

a*b* (ii) {aibjck | j = i + k}

Find a minimum-state FA for the following FA that recognizes the same language. OR1

Using the principle of mathematical induction, for all n ≥ 1, prove that, n (n+1) (n+2) 1×2+2 ×3+3 ×4 + .....+ n ×(n+1) =3

Check whether the following CFG is ambiguous or not with the help of word “abaa”. S → a | Sa | bSS | SSb | SbS

Using pumping lemma, prove that the language L = {an bn a bn+1 : for all n = 1, 2, 3 …} is nonregular.

Define - Chomsky Normal Form. Also convert the following CFG into its equivalent CNF. S → XaX | bX | Y X → XaX | XbX | ^ Y → ab

Define - total language tree. Also find out the same for the following CFG: S → aa | bX | aXX X → ab | b

Define - pumping lemma for context-free languages. Also prove that the language L = {xx | x ∈ {a, b}*} is not CFL with the help of the same.

Define - Equivalence relation. Decide whether each of the following relations on the set {1, 2, 3, 4} is an equivalence relation or not. Justify your answer with proper reason.

R = {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)}1 (ii) R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}2

Kill ^ - productions from the following CFG : S → AB | ^ A → aASb | a B → bS

Define - Pushdown Automaton and acceptance by a PDA

Convert the CFG with following productions into its equivalent PDA. Also trace out the same on input string abbaaa. S → a | aS | bSS | SSb | SbS

Consider the CFG with productions: S → aA | bC | b A → aS | bB B → aC | bA | a C → aB | bS Does this CFG generate the language containing all the words with an even number of a’s and an odd number of b’s over  = {a, b}? Prove your answer.

Explain Chomsky hierarchy in detail.

Design a PDA to accept strings with more a’s than b’s. Also trace out the same on input string abbabaa.

Define - Moore machine. Convert the following Moore machine into its equivalent Mealy machine.2

Define - Primitive Recursion. Also prove that the function, f ∶ N → Ndefined by f (x, y) = x + y is primitive recursive.

Draw Turing machine for L = {anbncn | n ≥ 0}. Also trace out the same on input string abc.

Discuss - Context Sensitive Language with example.

Describe recursive languages and recursively enumerable languages.

Define Turing Machine. Also draw Turing machine that accepts the language of palindromes over {a, b}.