Theory of Computation

Details

#### 1 Define automata? What are the difference between DFA and NFA?

Question Define automata? What are the difference between DFA and NFA? 2017

#### 2 What is binary relation? What are the property of binary relation.

Question What is binary relation? What are the property of binary relation. 2017

#### 3 Explain the following terms with example:Epsilon closures of NFAGrammar of l

Question Explain the following terms with example:Epsilon closures of NFAGrammar of language 2017

#### 4 Prove that, A language L is accepted by some DFA if and only if L is accepted by some NFA.

Question Prove that, A language L is accepted by some DFA if and only if L is accepted by some NFA. 2017

#### 5 Design DFA that accepts-Strings string with aba.Strings containing even numb

Question Design DFA that accepts-Strings string with aba.Strings containing even number 0's and even number of 1's. 2017

#### 6 Define regular expression.What are the applications of regular expression?

Question Define regular expression.What are the applications of regular expression? 2017

#### 7 Write the regular expression for the following languages:The set of strings that cons

Question Write the regular expression for the following languages:The set of strings that consists of alternating 0's and 1'sThe set of strings of 0's and 1's with at most one pair of consecutive 1'sThe set of strings a's and b's that starts with a and end with b 2017

#### 8 Convert the regular expression to E-NFA:(0+1)*1(0+1)(a|b)*abb(a|b)

Question Convert the regular expression to E-NFA:(0+1)*1(0+1)(a|b)*abb(a|b) 2017

#### 9 Define context free grammar and parse tree.

Question Define context free grammar and parse tree. 2017

#### 10 Write down the algorithm to remove useless symbols to simplify the context free grammar.

Question Write down the algorithm to remove useless symbols to simplify the context free grammar. 2017

#### 11 Consider the following grammar:S-aB|bAA-a|aS|bAAB-b|bs|ABBDerive the

Question Consider the following grammar:S-aB|bAA-a|aS|bAAB-b|bs|ABBDerive the string "aaabbabbba" be left most and rightmost derivation and draw the parse tree. 2017

#### 12 State and explain the pumping lemma for regular expression.

Question State and explain the pumping lemma for regular expression. 2017

#### 13 What is pushdown automata? Explain different ways of accepting language of pushdown automation.

Question What is pushdown automata? Explain different ways of accepting language of pushdown automation. 2017

#### 14 What are single tape and multiple track of Turing Machine.

Question What are single tape and multiple track of Turing Machine. 2017

#### 15 Define Turing Machine. What are the special features of Turing Machine ?

Question Define Turing Machine. What are the special features of Turing Machine ? 2017

#### 16 Design Turing Machine for the language {a^n b^n c^n |n&gt;=1}.

Question Design Turing Machine for the language {a^n b^n c^n |n>=1}. 2017

#### 17 Describe Instantaneous Description (ID) of a pushdown automata of input string 1111 with ne

Question Describe Instantaneous Description (ID) of a pushdown automata of input string 1111 with necessary figure. 2017

#### 18 Define decidable and undecidable problems.

Question Define decidable and undecidable problems. 2017

#### 19 Define finite automata? What is deductive and inductive proof?

Question Define finite automata? What is deductive and inductive proof? 2016

#### 20 What is the utility of finite automata in respect of Hardware and Software.

Question What is the utility of finite automata in respect of Hardware and Software. 2016

#### 21 Using deductive proof, proof if x&gt;=4 and 2x &lt;=x^2

Question Using deductive proof, proof if x>=4 and 2x <=x^2 2016

#### 22 Explain the following terms with necessary example:Binary alphabetPowe

Question Explain the following terms with necessary example:Binary alphabetPower of an alphabet 2016

#### 23 Design a DFA the accepts:String containing 001 sub stringString ending with

Question Design a DFA the accepts:String containing 001 sub stringString ending with 10 2016

#### 24 Design E-NFA that accepts the following decimal numbers:123.456123.

Question Design E-NFA that accepts the following decimal numbers:123.456123..456 2016

#### 25 What is regular expression? Write a regular expression to donate language L which accepts all the

Question What is regular expression? Write a regular expression to donate language L which accepts all the string which begin or end with either 00 or 11 2016

#### 26 Convert the following regular expression:01*;(0+1)01;00(0+1)*;

Question Convert the following regular expression:01*;(0+1)01;00(0+1)*; 2016

#### 27 Define a context free grammar? What are the application of context free grammar.

Question Define a context free grammar? What are the application of context free grammar.

#### 28 Define a context free grammar? What are the application of context free languages.

Question Define a context free grammar? What are the application of context free languages. 2016

#### 29 Design a CFG for palindromes and test for the string 0110

Question Design a CFG for palindromes and test for the string 0110 2016

#### 30 Explain the relationship between recursive, RE and Non-RE languages.

Question Explain the relationship between recursive, RE and Non-RE languages. 2016

#### 31 Define deterministic PDA.

Question Define deterministic PDA. 2016

#### 32 Convert the following Grammar to PDA that accept the same language by empty stack :S-

Question Convert the following Grammar to PDA that accept the same language by empty stack :S-aAAS-aS|bS|a 2016

#### 33 What is CNF? Convert the grammar of qus no. 5(c) to CNF.

Question What is CNF? Convert the grammar of qus no. 5(c) to CNF. 2016

#### 34 What is Turing Machine. Design a Turing Machine to add to given integers.

Question What is Turing Machine. Design a Turing Machine to add to given integers. 2016

#### 35 Design a Turing Machine and show how it behaves on a typical input that accepts the language {0^n

Question Design a Turing Machine and show how it behaves on a typical input that accepts the language {0^n 1^n|n>=1}. 2016

#### 36 Describe the pumping lemma for the CFL's.

Question Describe the pumping lemma for the CFL's. 2016

#### 37 What do you mean by intractability and decidability ? Explain

Question What do you mean by intractability and decidability ? Explain 2016

#### 38 What is finite automata? What is the reasons for studying automata theory in computer science?

Question What is finite automata? What is the reasons for studying automata theory in computer science? 2015

#### 39 Prove the theorem if x&gt;=4 then 2x&gt;=x^2 (using deductive proof)

Question Prove the theorem if x>=4 then 2x>=x^2 (using deductive proof) 2015

#### 40 Consider the following expressions:(a|b)*abbDraw the NFA with E-transition.

Question Consider the following expressions:(a|b)*abbDraw the NFA with E-transition. 2015

#### 41 What is regular expression? what are the rules for regular expression?

Question What is regular expression? what are the rules for regular expression? 2015

#### 42 A language L is accepted by some E-NFA if and only if L is accepted by some DFA.

Question A language L is accepted by some E-NFA if and only if L is accepted by some DFA. 2015

#### 43 Difference between NFA and DFA.

Question Difference between NFA and DFA. 2015

#### 44 What are the closure properties of regular expression ?

Question What are the closure properties of regular expression ? 2015

#### 45 what do you mean by context free grammar? Write the conventions for CFG derivations.

Question what do you mean by context free grammar? Write the conventions for CFG derivations. 2015

#### 46 Construct a CFG without E-production from the following grammar:S-a|Ab|aBaS-

Question Construct a CFG without E-production from the following grammar:S-a|Ab|aBaS-b|ES-b|A 2015

#### 47 What is ambiguity in CFG?

Question What is ambiguity in CFG? 2015

#### 48 Formally define a Pushdown Automata (PDA). Give a graphical notation of for a PDA.

Question Formally define a Pushdown Automata (PDA). Give a graphical notation of for a PDA. 2015

#### 49 Convert the following CFG expression into PDA-I-a|b|Ib|Ia|Io|I1E-I|E*E|E+E|(E)

Question Convert the following CFG expression into PDA-I-a|b|Ib|Ia|Io|I1E-I|E*E|E+E|(E) 2015

#### 50 Find the transitive closure reflexive and the transitive closure for the following relations-

Question Find the transitive closure reflexive and the transitive closure for the following relations-R={(1,2),(2,3),(3,4),(5,4)} 2015

#### 51 Explain Turing Machine Model.

Question Explain Turing Machine Model. 2015

#### 52 Generate the transit diagram for the Turing Machine that accepts the language {0^n 1^n|n&gt;0}

Question Generate the transit diagram for the Turing Machine that accepts the language {0^n 1^n|n>0} 2015

#### 53 Every language accepted by multiple Turing Machine is recursively enumerable-Explain that.

Question Every language accepted by multiple Turing Machine is recursively enumerable-Explain that. 2015

#### 54 Define decidable and undecidable problems.

Question Define decidable and undecidable problems. 2015

#### 55 Define finite automata, transition table, epsilon closure of NFA.

Question Define finite automata, transition table, epsilon closure of NFA. 2014

#### 56 What is binary relation. What are the properties of binary relations?

Question What is binary relation. What are the properties of binary relations? 2014

#### 57 Difference between NFA and DFA .

Question Difference between NFA and DFA . 2014

#### 58 Prove that each NFA is not DFA but every DFA is NFA.

Question Prove that each NFA is not DFA but every DFA is NFA. 2014

#### 59 Define Context Free Grammar, parse tree, useless symbols.

Question Define Context Free Grammar, parse tree, useless symbols. 2014

#### 60 What is pushdown automata. Describe in brief.

Question What is pushdown automata. Describe in brief. 2014

#### 61 What is chomskey normal from 3 prove that any context free language without E is generated by a g

Question What is chomskey normal from 3 prove that any context free language without E is generated by a grammar in which all production are of the form A-BC or A-a. 2014

#### 62 What is pushdown automata? Describe in brief.

Question What is pushdown automata? Describe in brief. 2014

#### 63 Describe about Moore machine and Mealy machines.

Question Describe about Moore machine and Mealy machines. 2014

#### 64 Describe applications of finite automata?

Question Describe applications of finite automata? 2014

#### 65 What is pumping lemma? Describe in detail.

Question What is pumping lemma? Describe in detail. 2014

#### 66 Write the procedure of eliminating E-transition .

Question Write the procedure of eliminating E-transition . 2014

#### 67 Define PDA formally.

Question Define PDA formally. 2014

#### 68 What is CNF and BNF.

Question What is CNF and BNF. 2014

#### 69 What are the applications of pumping lemma for CFL's.

Question What are the applications of pumping lemma for CFL's. 2014

#### 70 Give the formal definition of CFG.

Question Give the formal definition of CFG. 2014

#### 71 State the decidability of context free language.

Question State the decidability of context free language. 2014

#### 72 What do you mean by parsing ? What are the applications of parse tree.

Question What do you mean by parsing ? What are the applications of parse tree. 2014

#### 73 Define finite automata? What are the components of finite automata?

Question Define finite automata? What are the components of finite automata? 2013

#### 74 Explain the following terms with necessary examples:Binary AlphabetGrammar o

Question Explain the following terms with necessary examples:Binary AlphabetGrammar of LanguagePower of an AlphabetLanguage of Automata 2013

#### 75 What is the utility of finite automata in respect of hardware and software?

Question What is the utility of finite automata in respect of hardware and software? 2013

#### 76 What do you mean by transition table and transition diagram.

Question What do you mean by transition table and transition diagram. 2013

#### 77 Differentiate L*(Klene) and L+ (Positive).

Question Differentiate L*(Klene) and L+ (Positive). 2013

#### 78 Write an algorithm for minimizing number of states.

Question Write an algorithm for minimizing number of states. 2013

#### 79 what is the relation between Finite Automata and Regular Expression .

Question what is the relation between Finite Automata and Regular Expression . 2013

#### 80 What is the purpose of E transition? Construct NFA for (a+b)*b(a+b).

Question What is the purpose of E transition? Construct NFA for (a+b)*b(a+b). 2013

#### 81 Define left most , right most derivation and ambiguity.

Question Define left most , right most derivation and ambiguity.

#### 82 Find out the CFL for-S-aSb|aAbA-bAaA-ba.

Question Find out the CFL for-S-aSb|aAbA-bAaA-ba. 2013

#### 83 Write down the algorithm to remove useless symbols to simplify the CFG.

Question Write down the algorithm to remove useless symbols to simplify the CFG. 2013

#### 84 What is the pumping lemma? what are the applications of pumping lemma?

Question What is the pumping lemma? what are the applications of pumping lemma? 2013

#### 85 Prove that the states are equivalent if two states are not distinguish by the table filling algor

Question Prove that the states are equivalent if two states are not distinguish by the table filling algorithm. 2013

#### 86

Question What is pumping lemma? What are the applications of pumpinglemma? 2013

#### 87

Question Define homomorphism with an example.. Prove that h(L) is regular, if L is a regular language over alphabet I and h is a homomorphism on E. 2013

#### 88

Question Prove that the states are, equivalent if two states are notdistinguished by the table filling algorithm. 2013

#### 89

Question What is pushdown automata? Describe instantaneousdescriptions of a pushdown automata. 2013

#### 90

Question Design a PDA to accepts the following language : {0" l" I n 0}. 2013

#### 91

Question Prove that L = N (PN), if L be L (Ps) for some PDAPF = (Q, L r, go, Zo) then there is a PDA 4 P 2013

#### 92

Question What is BackuS-Naur Form (BNF)? 2013

#### 93

Question Define TudggmaChin Whatiare the special features of TM? 2013

#### 94

Question Define a more in TM, Differentiate between recursive andrecursively enumerable languages, 2013

#### 95

Question State thedecidabty of CFG. 2013

#### 96

Question Show that ambiguity problein'is un-decidable. 2013

#### 97

Question Define finite automata. What are the applitions of automatatheory. 2012

#### 98 What is tr

Question What is transition table and diagram? Draw the transition tableand diagram for 11(0 +1 )*. 2012

#### 99

Question Differentiate between NFA and DFA. 2012

#### 100

Question What is parse free? What are the disadvantages ofunambiguousparse tree. 2012

#### 101

Question Define Finite Automate. What is deductive and inductiveproof? 2011

#### 102

Question What is the utility of finite automate in respect of I hardware and Software. 2011

#### 103

Question Explain the following terms with necessary examples(i)Binary alphabet;(ii) Power of an alphabet. 2011

#### 104

Question Using pumping lemma show that the language L consistingof all string of l's whose length is a prime is not a regular language. 2011

#### 105

Question Design a INA that accepts strings containing 1010 assubstring. 2011

#### 106

Question 'What is difference between DFA and NFA? 2011

#### 107

Question What is the regular expression'? Write a regular expression todenote a language L which accepts all strings whichbegin or end with either 00 or 11. 2011

#### 108

Question What is the relationship between FA and regular expression? 2011

#### 109

Question Prove that, every language defined by regularexpression is also defined by a finite automate. 2011

#### 110

Question Define context free grammar. What are the application of context free languages? 2011

#### 111

Question What is a ambiguous grammar? The following grammar generates prefix expression with operands x and y binary operators +, — and *E--+EE I*EE] —EE x I y. 2011

#### 112

Question Design a CFG for palindromes and test for the strings 0110. 2011

#### 113

Question Convert the following regular expressions to NFA's with E -transitions (0+1)01. 2011

#### 114

Question Design a pushdown automaton which accepts a string, ofalphabet parenthesis 2011

#### 115

Question Convect the grammar to a pushdown automaton that acceptsthe language by empty stack.S —> OSI/A A —> i OA/S/E. 2011

#### 116

Question What are single tape and multiple track tape Turingmachine? 2011

#### 117 What is

Question What is a Turing machine? What are the possibilitiesof aTM when processing an input string? 2011

#### 118

Question Design a Turing machineand see how it behaves on a typical input and that accept the language 10"In n 2011

#### 119

Question What is Chomshey normal form? Show the notation ofTuring machine. 2011

#### 120

Question Define DFA and NFA. What arc the differences betweenDFA and NFA? 2010

#### 121

Question 2010

#### 122

Question Define regular expression. Write down the rules of regular expression. 2010

#### 123

Question Determine the regular expressions of the following :--(i) The set of all strings of a's and b's;(ii) The set of all strings of a's and .b's of length two.,(iii) The set of all strings containing zero or more instances of a or b;(iv) The set of all string. of zero or more a's. 2010

#### 124

Question Convert the regular expression to an E - NFA(i) (0+ 1)*1 (0+ 1)(ii) (a I b)* obi) (a I h). 2010

#### 125

Question Write an algorithm for minimizing number of states. 2010

#### 126 Define symbol, st

Question Define symbol, string and alphabet. 2010

#### 127

Question define a context-free-grammar that has only string in L(G) area" h" for11 > f. 2010

#### 128 Explain Chomsky N

Question Explain Chomsky Normal form with example 2010

#### 129

Question Define leftmost, rightmost derivation and ambiguity 2010

#### 130

Question Write down an algorithm to remove useless symbols to simplifythe context free grammar. 2010

#### 131

Question Define Pushdown Automaton and explain difference ways ofaccepting language of pushdown automaton 2010

#### 132

Question Explain PDA that accepts{WW" W in (0 + 1)*) by emptystack. 2010

#### 133

Question Explain Turing Machines and ID of Turing Machines. 2010

#### 134

Question Show the computation of Turing Machine for the string 000111using ID. 2010

#### 135

Question Explain Multitape Turing Machine with example 2010

#### 136

Question Define Decidable and Undecidable problems 2010

#### 137 Prove theAn odd positive integer n can be written as n = 2k + 1, for someinteger k &g

Question Prove theAn odd positive integer n can be written as n = 2k + 1, for someinteger k ≥ 0. East West University 2013

#### 138 prove the There exist irrational numbers x and y such that x power (y) is rational

Question prove the There exist irrational numbers x and y such that x power (y) is rational Ahsanullah Institute of Information and Communication Technology 2013

#### 139 For every prime number p, prove that &radic;p is irrational.

Question For every prime number p, prove that √p is irrational. North South University 2013

#### 140 Let n be a positive integer that is not a perfect square. Prove that &radic;n is irrational.

Question Let n be a positive integer that is not a perfect square. Prove that √n is irrational. Tejgaon College 2012

#### 141 Prove by induction that n power(4) &minus; 4n power(2) is divisible by 3, for all integers n &ge;

Question Prove by induction that n power(4) − 4n power(2) is divisible by 3, for all integers n ≥ 1. Tejgaon College 2013

#### 142 Prove that in any set of n + 1 numbers from {1, 2, . . . , 2n}, there are always two numbers that

Question Prove that in any set of n + 1 numbers from {1, 2, . . . , 2n}, there are always two numbers that are consecutive. Shaikh Burhanuddin Post Graduate College 2014

#### 143 Prove that in any set of n + 1 numbers from {1, 2, . . . , 2n}, there are always two numbers such

Question Prove that in any set of n + 1 numbers from {1, 2, . . . , 2n}, there are always two numbers such that one divides the other. Ahsanullah Institute of Information and Communication Technology 2013

#### 144 Define theThe pumping lemma and nonregular languages

Question Define theThe pumping lemma and nonregular languages Abudharr Gifari College 2012

#### 145 Proof of Higman&rsquo;s Theorem

Question Proof of Higman’s Theorem Dhaka College 2014

#### 146 For each of the following languages, construct an NFA, with the specifiednumber of states,

Question For each of the following languages, construct an NFA, with the specifiednumber of states, that accepts the language. In all cases, the alphabet is{0, 1}.1. The language {w : w ends with 10} with three states.2. The language {w : w contains the substring 1011} with five states.3. The language {w : w contains an odd number of 1s or exactly two 0s}with six states. North South University 2013

#### 147 Give regular expressions describing the following languages. In allcases, the alphabet is {

Question Give regular expressions describing the following languages. In allcases, the alphabet is {0, 1}.1. {w : w contains at least three 1s}.2. {w : w contains at least two 1s and at most one 0},3. {w : w contains an even number of 0s and exactly two 1s}.4. {w : w contains exactly two 0s and at least two 1s}.5. {w : w contains an even number of 0s and each 0 is followed by at least one 1}.6. {w : every odd position in w is 1} East West University 2013

#### 148 Convert each of the following regular expressions to an NFA.1. (0 &cup; 1)&lowast;000(0 &cu

Question Convert each of the following regular expressions to an NFA.1. (0 ∪ 1)∗000(0 ∪ 1)∗2. (((10)∗(00)) ∪ 10)∗3. ((0 ∪ 1)(11)∗ ∪ 0)∗ East West University 2014

#### 149 If n &ge; 1 is an integer and w = a1a2 . . . an is a string, then for any iwith 0 &le; i &l

Question If n ≥ 1 is an integer and w = a1a2 . . . an is a string, then for any iwith 0 ≤ i < n, the string a1a2 . . . aiis called a proper prefix of w. (If i = 0,then a1a2 . . . ai = ǫ.)For any language L, we define MIN(L) to be the languageMIN(L) = {w ∈ L : no proper prefix of w belongs to L}.Prove the following claim: If L is a regular language, then MIN(L) is regularas well. East West University 2014

#### 150 Let  ={a,b}. Draw a DFA that will accept set of strings beginning with a andending with b.

Question Let  ={a,b}. Draw a DFA that will accept set of strings beginning with a andending with b. College of Business Science & Technology 2013

#### 151 What is the difference between transition function and extended transition function? What is the

Question What is the difference between transition function and extended transition function? What is the purpose of defining extended transition function? North South University 2015

#### 152 Let  ={0-9,.} Design a DFA that will accept set of both integer numbers and floatnumbers.

Question Let  ={0-9,.} Design a DFA that will accept set of both integer numbers and floatnumbers. East West University 2015

#### 153 What is the definition of a DFA?

Question What is the definition of a DFA? Ahsanullah Institute of Information and Communication Technology 2015

#### 154 What is regular expression? (2017,

Question What is regular expression? (2017,2016,2015,2010) 