**Theory of Computation**

**Topic-1: Review of Mathematical Theory**

**Question **1** **Define onto function. In each case, a relation on the set {1, 2, 3} is given. Of the three properties, reflexivity, symmetry, and transitivity, determine which ones the relation has. Give reasons.

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

R={(1, 1),(2,2), (3,3),(1,2)} c.R=φ

**Question **2 Write Principle of Mathematical Induction. Prove that for every n≥1,

∑_{i=1} ^{n} 1/ i(1+1) = n/(n+1)

**Question **3 Define one-to-one, onto and bijection function.

**Question **4**.** Check whether the function f:R+R,f(x)=x2 is one to one and onto.

**Question **5** **Explain equivalence relation with example.

**Question **6** **Using Principle of Mathematical Induction, prove that for every n>=1

n

Σ_{i=n }(n+1)/2i=0

**Question **7 Prove that √2 is Irrational by method of Contradiction

**Question **8 Define onto and one-to-one functions.

**Question **9 Give recursive definition of a tree.

**Question **10 Consider the relation R = {(1,2), (1,1), (2,1), (2,2), (3,2), (3,3)} defined over {1, 2, 3}. Is it reflexive? Symmetric? Transitive? Justify each of your answers.

**Question **11 Draw truth table for following logic formula:

P(¬PV¬Q). Is it a tautology? A contradiction? Or neither? Justify your answer.

**Question **12 Use the principle of mathematical induction to prove that

1+3+5+...+ r = n^{2} for all n> 0 where r is an odd integer & n is the number of terms in the sum. (Note: r = 2n-1)

**Question **13 Let A ={1,2,3,4,5,6} and R be a relation on A such that a R b iff a is a multiple of b. Write R. Check if the relation is

i)Reflexive ii)Symmetric iii)Asymmetric iv)Transitive

**Question **14 Define One-to-one and Onto Functions. Also explain Compositions and Inverse of functions.

**Question **15 Define Mathematical Induction Principle and Prove that for every n ≥ 1,

^{n}Σ_{i=1} i^{2} = n (n+1)(2n+1)/ 6

**Question **16 Prove the formula(00*1)*1= 1+0(0+10)*11

**Question **17 Define one-to-one, onto and bijection function.

**Question **18 Explain reflexivity, symmetry, and transitivity properties of relations.

**Question **19 State the principle of mathematical induction and prove by mathematical induction that for all positive integers n 1+2+3+........+n = n(n+1)/2.

**Question **20 Prove by mathematical induction: for every n>=1, 1+3+5+...+(2n-1) = n^{2}

**Question **21 Define - bijection function. Check whether the function defined by is a bijection function or not. Justify your answer.

**Question **22 Write the principle of Mathematical Induction. Prove using mathematical induction that for every n ≥ 0,

^{n}Σ_{i=1} 1/i(1+1) = n/(n+1)

(Consider the sum on the left is 0 for n = 0)

**Question **23 Define-Equivalence relation. A relation n the set{1,2,3} is given as R = {(a, b) | a - b is an even no}. Check whether R is equivalence relation or not. Give reasons.

**Topic 2: Regular Languages and Finite Automata**

**Question **1 Find a regular expression corresponding to each of the following subsets of {0,1}*

The language of all strings that begin or end with 00 or 11.

The language of all strings containing both 11 and 010 as substrings.

**Question **2 Write RE for the languages of all Strings that do not end with 01.

**Question **3 Give recursive definition of regular expressions. State the hierarchy of the operators used in regular expressions.

**Question **4 Write a regular expression for language L over {0,1} such that every string in L

i) Begins with 00 and ends with 11.

ii) Contains alternate 0 and 1.

**Question **5 Write Regular Expressions corresponding to each of the following subsets of {0,1}*

i) The language of all strings in{0,1}* that containing at least two 0`s.

ii) The language of all strings containing both 101 and 010 as substrings.

iii) The language of all strings that do not end with 01.

**Question **6 What are the closure properties of regular languages?

**Question **7 Find a regular expression corresponding to each of the following subsets of {0,1}*

i) The language of all strings that begin or end with 00 or 11.

ii) The language of all strings beginning with 1 and ending with 0.

**Question **8 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

**Question **9 What are the applications of regular expressions and finite automata?

**Question **10 Write Regular Expression over the alphabets{a, b} consisting strings:

i. Second last character as `a`

ii. Starting with `a` and ending with `b`

**Question **11 Prove that if L1 and L2 are regular languages then L1∩L2 is also a regular language.

**Question **12 Show using pumping lemma that the given language is not a CFL. L={a^{n}b^{2n}a^{n}|n≥0}

**Question **13 Give recursive definitions of the extended transition functions, δ* for DFA and NFA.

**Question**14 Use the pumping lemma to show that following language is not regular. L={xy | x, y ε {0, 1}* and y is either x or x^{r}}

**Question** 15 Let M1, M2 and M3 be the FAs pictured in Figure, recognizing languages L1, L2 and L3, respectively.

**Question **16 Compare FA, NFA and NFA_{-}^{^}.

**Question** 17 Draw a FA for following regular language.

(i) (11+110)*0 (ii)(0+1)*(10+11)

**Question **18 Design a moore machine to determine residue number 3 for binary number.

**Question **19 Write Kleene`s Theorem part-I, Any regular language can be accepted by a finite automation

**Question **20 Define DFA and NFA and NFA-Λ

**Question** 21 Give recursive definitions of the extended transition functions, δˆ(i.e., for strings) for DFA and NFA.

**Question **22 Convert the given Moore machine into Mealy machine. Draw state transition diagram of Mealy machine.

**Question **23 Figure shows NFA-^. Draw an FA accepting the same language.

**Question **24 Explain `finite state machines without puts`. Discriminate between Mealy and Moore machines.

**Question **25 Use Pumping Lemma to show that L={x∈{0,1}* | x is a palindrome} is not a regular language.

**Question **26 Design a FA for the regular expression (0+1)(01)*(011)*

Draw FAs recognizing the following languages.

a. L1 UL2

b. L1 ∩L3

**Question **27 There are 2 languages over

∑= {a, b}L1= all strings with a double `a`

L2 = all strings with an even number of `a`

Find a regular expression and an FA that define L1∩L2

**Question **28** **If L={0^{i}1^{i}|i≥0} Prove that L is regular.

**Question **29 Prove Kleene`s Theorem (Part I): Any Regular Language can be accepted By a Finite Automaton(FA).

**Question **30 Define NFA-Λ. Explain how to convert NFA- Λ in to NFA and FA with Suitable example.**Question **31 Convert following NFA- Λ to NFA (NOV-2017)

**Question **33 Draw FA for accepting:

i) The string in {0,1}* ending in 1 and not containing substring 00.

ii) The strings with odd no of 1`s and odd no of 0`s.

**Question **34 Explain Pumping Lemma and its applications.

**Question **35 Prove Kleene`s Theorem Part1 with illustration.

**Question **36 Minimize the DFA shown in Fig.

**Question **37 Consider the NFA- Λ depicted in following table:

i) Compute the Λ-closure of each state.

ii) Convert the NFA- Λ to a DFA

**Question **38 Convert the Moore machine shown in Fig. into an equivalent Mealy Machine.

**Question **39 Convert the NFA given in Table below to its corresponding DFA and draw the DFA.

**Question **40** **Convert the Mealy machine show in given figure into Moore machine.

**Question **41 Fig. shows two DFAs M1 and M2, to accept languages L1 and L2, respectively. Determine DFAs to recognize L1UL2.

**Question **42 Explain moore machine and mealy machine.

**Question **43 What are the applications of finite automata? Draw Finite Automata to accept following.

The language accepting strings ending with `01` over input alphabets Σ={0, 1}

(i) The language accepting strings ending with `abba` over input alphabets Σ ={a, b}

**Question **44 State pumping lemma for regular languages.(WINTER2018) 03

**Question **45 Write difference between DFA and NDFA. Convert the following NDFA to DFA

**Question **46 Define NFA- ∧. Explain how to convert NFA-∧ into NFA and FA with suitable example

**Question **47 Compare FA, NFA and NFA-^

**Question **48 Design Moore machine to generate 1`s complement of binary number

**Question **49 Draw FA for following languages:L1 = {w | 00 is not substring of w}L2={w|wendsin01}

Find FA accepting languages

(i).L1 UL2 and (ii).L1L2

**Question **50 Give the left linear grammar for RE(10)* 1

**Question **51 Minimize the given DFA:

**Question **52 Construct finite automata for following left linear grammar:

S >X0 |Y1

X >Y1

Y >Y0|1

**Question **53 Compare PDA with FSM

**Question **54 Write a note on DPDA and NPDA

**Question **55 Design a pushdown automata

to check well-formed parenthesis.

**Question **56 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.

**Question **57 Give transition table for PDA recognizing the following language and trace them oveof the machine for input string abcba:

L ={xcxr| x∈*a,b}∗}

**Question **58 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.

**Question **59 LetFA1andFA2 be the FAs as shown in the figure recognizing the languages L1 and L2 respectively. Draw an FA recognizing the language, L1 U L2.

**Question **60 Define - Moore machine. Convert the following Moore machine into its equivalent Mealy machine:

**Question **61 Convert the following NFA -∧ into its equivalent DFA that accepts the same language:(NOV-2019)

**Question **62 Find a minimum-state FA for the following FA that recognizes the same language using the minimization algorithm:(NOV-2019)

**Question **63 Show using the pumping lemma that the following language is not a CFL.

L= {aibjck| i < j

**Unit 3: Context Free Grammar**

**Question **1 Show that the CFG with productions

S-> a|Sa|bSS|SSb|SbS is ambiguous.

**Question **2 Given the context- free grammar G,find a CFGG` in Chomsky Normal Form.

G:

S--> AaA |CA|BaB

A --> aaBa | CDA | aa | DCB-->bB|bAB |bb|aS C-->Ca|bC |D

D-->bD|ε

ε represents null.

**Question **3 Explain Chomsky Hierarchy.

**Question **4 Define Context Free Grammar. Find context-free grammar for the language:={aibj|i <2j}

**Question **5 Explain Union Rule and Concatenation Rule for Context-Free Grammar.

**Question **6 Let G be the grammar

S->aB|bA

A->a|aS|bAA B->b|bS|aBB

For string aaabbabbba, find Leftmost derivation and Rightmost derivation.

**Question **7 Given the Context Free Grammar G, find a CFGG` in Chomsky Normal Form generating L(G)- { }

S→aY|Ybb|Y

X→ /|a Y→aXY|bb|XXa

**Question **8 Define CFG. When is a CFG called an `ambiguous CFG`?

**Question **9 Give the recursive definition of the iterated derivation (i.e., derivation in zero or more steps), denoted as =>. Give mathematical description of the language of a CFG.

**Question **10 Consider following grammar:

S->A1B

A->0A|Λ 07

B->0B|1B|Λ

Give leftmost and rightmost derivations of the string 00101. Also draw the parse tree corresponding to thi string.

**Question **11 Define CFG. When is a CFG called an `ambiguous CFG`

**Question **12 Consider following grammar:

S--->ASB|Λ A >aAS|a

B >SbS|A|bb

Eliminate useless symbols, if any.

Eliminate Λ productions.

**Question **13 Convert the CFG,G({S,A,B},{a,b},P,S) to CNF, where P is as follows

S--> aAbB A-->Ab|b B-->Ba|a

**Question **14 Prove that the following CFG is Ambiguous.

S->S +S |S* S |a|b

Write the unambiguous CFG based on precedence rules for the above grammar. Derive the parse tree for expression (a+a)*b from the

unambiguous grammar.

**Question **15 Check whether the given grammar is in CNFS->bA|aB

A->bAA|aS|a B->aBB|bS|b

If it is not in CNF, Find the equivalent CNF.

**Question **16 Give the context free grammar for the following languages.

(011+1)*(01)*

**Question **17 Explain Union Rule and Concatenation Rule for Context Free Grammar

**Question **18 Define Context-Sensitive Grammar. What is the language of following context-sensitive grammar?

S--->aTb|ab

aT--->aaTb|ac

**Question **19 Define CFG. When a CFG is called an `ambiguous CFG`?**Question **20 Define 1)Parse tree 2)Ambiguous grammar

**Question **21 Consider the grammar:

T--> ABA

A---> aA|∈

B -->bB|∈Is given grammar ambiguous? If so then remove ambiguity

**Question **22 Find context free grammar for the following language.

L1={aibjck|i=j+k},L2=(011+1)*(01)*,L3=(0+1)1*(1+(01)*)

**Question **23 Eliminate useless symbols,∈-productions and unit productions for the following grammar:

S---->0A0|1B1|BB, A--->C, B--->S|A, C >S|∈

**Question **24 Consider the grammar:

S --->aAS|a

A --->SbA|SS|ba.

Derive leftmost and rightmost derivation of string aabbaa using given grammar.

**Question **25 Give CFG for following languages:

1).L=a*b*2).L= {a^{n+2}b^{n}|n>=0}

**Question **26 Define - ambiguous grammar, leftmost derivation. Check whether the following grammars are ambiguous or not. Justify your answer with proper reason.

S → ABA

A → aA | ∧ B→bB|∧

S → A| B

A → aAb | aabb

B→ abB| ∧ 07

**Question **27 Describe the language generated by the following grammars:

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

**Question **29 Convert the following CFG into its equivalent CNF:

**Unit 4: Push Down Autimata, CFL and NCFL**

**Question **1 Decide whether the given language is a CFL, and prove your answer. L={xyx|x, yε{a,b}* and |x|≥ 1}

**Question **2 Construct PDA for

S --- >0AB

A >1A|1

B >0B|1A|0

Trace the string 01011 using PDA.

**Question **3 Give transition tables for deterministic PDA recognizing following language: L={xε{a,b}* |n a(x)≠ nb(x)}

Trace it for the string abbaababbb

**Question **4 Prove that There are CFLs L1 and L2 so that L1∩L2 is not a CFL, and There is a CFL L so that L` is not a CFL.

**Question **5 For the language L={xcxr|xε{a,b}*} design a PDA (PushDown Automata).

**Question **6 For the PDA, ({q0 , q 1},{0, 1},{0,1, z0 },δ, q 0 , z0, φ ),

where δ is

δ(q0 , ε,z0 ) ={(q1, ε)}

δ(q0 , 0,z0 )={(q0 ,0z0 )}

δ(q0 ,0, 0)={(q0 , 00)}

δ(q0 ,1, 0)={(q0 , 10)}

δ(q0 ,1, 1)={(q0 , 11)}

δ(q0 ,0, 1)={(q1 , ε)}

δ(q1 ,0, 1)={(q1 , ε)}

δ(q1 ,0, 0)={(q1 , ε)}

δ(q1 , ε,z0 ) ={(q1, ε)}

Obtain CFG accepted by the above PDA.

**Question **7 Give formal definition of PDA. Give mathematical description of `acceptance of a string by a PDA by empty stack`.

**Question **8 Convert the following grammar to a PDA:

I-> a|b|Ia|Ib|I0|I1

E->I|E* E|E+E|(E) 07

**Question **9 Using pumping lemma for CFL`s, show that the language L={a^{m}b^{m}c^{n} |m≤n≤2m} is not context free.

**Question **10 Given a CFG , G =( {S,A,B},{0,1},P,S) with P as follows S-->0B|1A

A --> 0S|1AA|0 B-->1S|0BB|1

Design a PDAM corresponding to CFG, G. Show that the string 0001101110 belongs to CFL, L(G)

**Question **11 Design a PDA, M to accept L={ a^{n}b ^{2n}|n ≥ 1 }

**Question **12 Define Push Down Automata (PDA). Design and draw a deterministic PDA accepting strings with more a`s than b`s. Trace it for the string `abbabaa`.

**Question **13 Write PDA for following languages:

{a^{i}b^{j}c^{k}|i,j,k>=0 and j=i or j= k}.

**Question **14 What is CNF? Convert the following CFG into CNF. S → ASA | aB, A →B|S, B→ b |ε

**Question **15 Define PDA. Describe the pushdown automata for language{0^{n}1^{n} | n≥0}.

**Question **16 Explain pushdown automata with example and their application in detail.

**Question **17 Define grammar and Chomsky hierarchy.

**Question **18 Prove that - `If there is a CFG for the language L that has no ∧- productions, then there is a CFG for L with 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

**Question **19. Write CFG for the following languages:

i. {a^{i}b^{j}c^{k} |i = j+ k}

ii. {a^{i}b^{j}c^{k} |j =i orj= k}

**Question **20 Prove that the language L={a^{n}b^{n}ab^{n+1}|n=1,2,3,...+ is non regular using pumping lemma.

**Question **21 Convert the following CFG into its equivalent PDA

**Unit 5:Turing Machine**

**Question **1 Define Context-Sensitive Grammar. Write a CSG for {anbncn|n≥1}.

**Question **2 Draw a transition diagram for a Turing machine for the language of all Palindromes over{a, b}.

**Question **3 Write Short note on Church-Turing Thesis.

**Question **4 Draw a transition diagram for a Turing machine accepting the language {SS|Sε{a, b}*}.

**Question **5 Draw a Turing Machine(TM) to accept Even and odd Palindromes over {a,b}.

**Question **6 Write a short note on Universal Turing Machine.

**Question **7 Write a Turing Machine to copy strings.

**Question **8 Give definition of Turing Machine. What do you mean by an Instantaneous description of a Turing Machine?

**Question **9 Describe recursive languages and recursively enumerable languages.

**Question **10 Design a Turing machine to accept the language{0n1n|n≥1}.

**Question **11 Design a Turing machine for the language over{0,1}containing strings With equal number of 0`sand1`s.

**Question **12 Draw a Turing Machine(TM) to accept Palindromes over{a,b}.(Even as Well as Odd Palindromes)

**Question **13 Draw a transition diagram for a Turing machine accepting the following language.{anbncn|n ≥0 }

**Question **14 Explain Universal Turing machine with the help of an example

**Question **15 Draw the TM which recognize words of the form{an bn cn| n>=1}.

**Question **16 Explain Universal Turing Machine and Church Turing Hypothesis.

**Question **17 What is Turing Machine? Write advantages of TM over FSM.

**Question **18 Write a short note on Universal Turing Machine

**Question **19 Draw a transition diagram for a Turing machine for the language of all palindromes over{a,b}

**Question **20 Write a short note on church-turing thesis.

**Question **21 Give the formal definition of Turing machine. Also compare the power of DFA, NFA, DPDA, NDPA and TM

**Question **22 Write a note on post machines

**Question **23 Design a Turing machine to reverse the string over alphabet{0,1}

**Question **24 Compare and contrast push down automata and Turing machine

**Question **25 Enlist limitations of Turing machines.

**Question **26 Design a Turing machine which accepts the language consisting string Which contain abaasa substring over alphabets{a,b}

**Question **27 Discuss universal Turing machine

**Question **28 Discuss-Non deterministic Turing Machines and Universal Turing Machines

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

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

**Unit 6: Computable Functions**

**Question **1 Show that the function f(x,y)=x+y is primitive recursive

**Question **2 Define Constant functions, Successor functions and Projection function.

**Question **3 Write a short note on μ-recursive function.

**Question **4 Briefly describe following terms:(1) halting problem(2) undecidable problem

**Question **5 Define functions by Primitive Recursion. Show that the function f(x,y)=x+y is primitive recursive.

**Question **6 Write Short note on Following:

i) Halting Problem

ii) Primitive Recursive Function.

**Question **7 Describe recursive languages and recursively enumerable languages.**Question **8 Explain primitive recursive function by suitable example.

**Question **9 Write a short note on Halting problem

**Question **10 What is decidability? How to prove that the given language is undecidable? List some undecidable problems.

**Question **11 Define - Primitive recursive functions and also give complete primitive recursive derivations for the function, f : N → N defined by Add(x, y) = x+ y.