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 ⁿ  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² 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,

ⁿΣ_i=1 i² = 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²

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,

ⁿΣ_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ⁿb²ⁿaⁿ|n≥0}

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

Question14 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ⁱ1ⁱ|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 <k}

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ⁿ⁺²bⁿ|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^mb^mcⁿ |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ⁿb ²ⁿ|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ⁱb^jc^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ⁿ1ⁿ | 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ⁱb^jc^k |i = j+ k}
ii. {aⁱb^jc^k |j =i orj= k}

Question 20 Prove that the language L={aⁿbⁿabⁿ⁺¹|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.