Theory of Computation
Question Define automata? What are the difference between DFA and NFA?
NU Year 2017
Question What is binary relation? What are the property of binary relation.
NU Year 2017
Question Explain the following terms with example:Epsilon closures of NFAGrammar of language
NU Year 2017
Question Prove that, A language L is accepted by some DFA if and only if L is accepted by some NFA.
NU Year 2017
Question Design DFA that accepts-Strings string with aba.Strings containing even number 0's and even number of 1's.
NU Year 2017
Question Define regular expression.What are the applications of regular expression?
NU Year 2017
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
NU Year 2017
Question Convert the regular expression to E-NFA:(0+1)*1(0+1)(a|b)*abb(a|b)
NU Year 2017
Question Define context free grammar and parse tree.
NU Year 2017
Question Write down the algorithm to remove useless symbols to simplify the context free grammar.
NU Year 2017
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.
NU Year 2017
Question State and explain the pumping lemma for regular expression.
NU Year 2017
Question What is pushdown automata? Explain different ways of accepting language of pushdown automation.
NU Year 2017
Question What are single tape and multiple track of Turing Machine.
NU Year 2017
Question Define Turing Machine. What are the special features of Turing Machine ?
NU Year 2017
Question Design Turing Machine for the language {a^n b^n c^n |n>=1}.
NU Year 2017
Question Describe Instantaneous Description (ID) of a pushdown automata of input string 1111 with necessary figure.
NU Year 2017
Question Define decidable and undecidable problems.
NU Year 2017
Question Define finite automata? What is deductive and inductive proof?
NU Year 2016
Question What is the utility of finite automata in respect of Hardware and Software.
NU Year 2016
Question Using deductive proof, proof if x>=4 and 2x <=x^2
NU Year 2016
Question Explain the following terms with necessary example:Binary alphabetPower of an alphabet
NU Year 2016
Question Design a DFA the accepts:String containing 001 sub stringString ending with 10
NU Year 2016
Question Design E-NFA that accepts the following decimal numbers:123.456123..456
NU Year 2016
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
NU Year 2016
Question Convert the following regular expression:01*;(0+1)01;00(0+1)*;
NU Year 2016
Question 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 languages.
NU Year 2016
Question Design a CFG for palindromes and test for the string 0110
NU Year 2016
Question Explain the relationship between recursive, RE and Non-RE languages.
NU Year 2016
Question Define deterministic PDA.
NU Year 2016
Question Convert the following Grammar to PDA that accept the same language by empty stack :S-aAAS-aS|bS|a
NU Year 2016
Question What is CNF? Convert the grammar of qus no. 5(c) to CNF.
NU Year 2016
Question What is Turing Machine. Design a Turing Machine to add to given integers.
NU Year 2016
Question Design a Turing Machine and show how it behaves on a typical input that accepts the language {0^n 1^n|n>=1}.
NU Year 2016
Question Describe the pumping lemma for the CFL's.
NU Year 2016
Question What do you mean by intractability and decidability ? Explain
NU Year 2016
Question What is finite automata? What is the reasons for studying automata theory in computer science?
NU Year 2015
Question Prove the theorem if x>=4 then 2x>=x^2 (using deductive proof)
NU Year 2015
Question Consider the following expressions:(a|b)*abbDraw the NFA with E-transition.
NU Year 2015
Question What is regular expression? what are the rules for regular expression?
NU Year 2015
Question A language L is accepted by some E-NFA if and only if L is accepted by some DFA.
NU Year 2015
Question Difference between NFA and DFA.
NU Year 2015
Question What are the closure properties of regular expression ?
NU Year 2015
Question what do you mean by context free grammar? Write the conventions for CFG derivations.
NU Year 2015
Question Construct a CFG without E-production from the following grammar:S-a|Ab|aBaS-b|ES-b|A
NU Year 2015
Question What is ambiguity in CFG?
NU Year 2015
Question Formally define a Pushdown Automata (PDA). Give a graphical notation of for a PDA.
NU Year 2015
Question Convert the following CFG expression into PDA-I-a|b|Ib|Ia|Io|I1E-I|E*E|E+E|(E)
NU Year 2015
Question Find the transitive closure reflexive and the transitive closure for the following relations-R={(1,2),(2,3),(3,4),(5,4)}
NU Year 2015
Question Explain Turing Machine Model.
NU Year 2015
Question Generate the transit diagram for the Turing Machine that accepts the language {0^n 1^n|n>0}
NU Year 2015
Question Every language accepted by multiple Turing Machine is recursively enumerable-Explain that.
NU Year 2015
Question Define decidable and undecidable problems.
NU Year 2015
Question Define finite automata, transition table, epsilon closure of NFA.
NU Year 2014
Question What is binary relation. What are the properties of binary relations?
NU Year 2014
Question Difference between NFA and DFA .
NU Year 2014
Question Prove that each NFA is not DFA but every DFA is NFA.
NU Year 2014
Question Define Context Free Grammar, parse tree, useless symbols.
NU Year 2014
Question What is pushdown automata. Describe in brief.
NU Year 2014
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.
NU Year 2014
Question What is pushdown automata? Describe in brief.
NU Year 2014
Question Describe about Moore machine and Mealy machines.
NU Year 2014
Question Describe applications of finite automata?
NU Year 2014
Question What is pumping lemma? Describe in detail.
NU Year 2014
Question Write the procedure of eliminating E-transition .
NU Year 2014
Question Define PDA formally.
NU Year 2014
Question What is CNF and BNF.
NU Year 2014
Question What are the applications of pumping lemma for CFL's.
NU Year 2014
Question Give the formal definition of CFG.
NU Year 2014
Question State the decidability of context free language.
NU Year 2014
Question What do you mean by parsing ? What are the applications of parse tree.
NU Year 2014
Question Define finite automata? What are the components of finite automata?
NU Year 2013
Question Explain the following terms with necessary examples:Binary AlphabetGrammar of LanguagePower of an AlphabetLanguage of Automata
NU Year 2013
Question What is the utility of finite automata in respect of hardware and software?
NU Year 2013
Question What do you mean by transition table and transition diagram.
NU Year 2013
Question Differentiate L*(Klene) and L+ (Positive).
NU Year 2013
Question Write an algorithm for minimizing number of states.
NU Year 2013
Question what is the relation between Finite Automata and Regular Expression .
NU Year 2013
Question What is the purpose of E transition? Construct NFA for (a+b)*b(a+b).
NU Year 2013
Question Define left most , right most derivation and ambiguity.
Question Find out the CFL for-S-aSb|aAbA-bAaA-ba.
NU Year 2013
Question Write down the algorithm to remove useless symbols to simplify the CFG.
NU Year 2013
Question What is the pumping lemma? what are the applications of pumping lemma?
NU Year 2013
Question Prove that the states are equivalent if two states are not distinguish by the table filling algorithm.
NU Year 2013
Question What is pumping lemma? What are the applications of pumpinglemma?
NU Year 2013
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.
NU Year 2013
Question Prove that the states are, equivalent if two states are notdistinguished by the table filling algorithm.
NU Year 2013
Question What is pushdown automata? Describe instantaneousdescriptions of a pushdown automata.
NU Year 2013
Question Design a PDA to accepts the following language : {0" l" I n 0}.
NU Year 2013
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
NU Year 2013
Question What is BackuS-Naur Form (BNF)?
NU Year 2013
Question Define TudggmaChin Whatiare the special features of TM?
NU Year 2013
Question Define a more in TM, Differentiate between recursive andrecursively enumerable languages,
NU Year 2013
Question State thedecidabty of CFG.
NU Year 2013
Question Show that ambiguity problein'is un-decidable.
NU Year 2013
Question Define finite automata. What are the applitions of automatatheory.
NU Year 2012
Question What is transition table and diagram? Draw the transition tableand diagram for 11(0 +1 )*.
NU Year 2012
Question Differentiate between NFA and DFA.
NU Year 2012
Question What is parse free? What are the disadvantages ofunambiguousparse tree.
NU Year 2012
Question Define Finite Automate. What is deductive and inductiveproof?
NU Year 2011
Question What is the utility of finite automate in respect of I hardware and Software.
NU Year 2011
Question Explain the following terms with necessary examples(i)Binary alphabet;(ii) Power of an alphabet.
NU Year 2011
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.
NU Year 2011
Question Design a INA that accepts strings containing 1010 assubstring.
NU Year 2011
Question 'What is difference between DFA and NFA?
NU Year 2011
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.
NU Year 2011
Question What is the relationship between FA and regular expression?
NU Year 2011
Question Prove that, every language defined by regularexpression is also defined by a finite automate.
NU Year 2011
Question Define context free grammar. What are the application of context free languages?
NU Year 2011
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.
NU Year 2011
Question Design a CFG for palindromes and test for the strings 0110.
NU Year 2011
Question Convert the following regular expressions to NFA's with E -transitions (0+1)01.
NU Year 2011
Question Design a pushdown automaton which accepts a string, ofalphabet parenthesis
NU Year 2011
Question Convect the grammar to a pushdown automaton that acceptsthe language by empty stack.S —> OSI/A A —> i OA/S/E.
NU Year 2011
Question What are single tape and multiple track tape Turingmachine?
NU Year 2011
Question What is a Turing machine? What are the possibilitiesof aTM when processing an input string?
NU Year 2011
Question Design a Turing machineand see how it behaves on a typical input and that accept the language 10"In n
NU Year 2011
Question What is Chomshey normal form? Show the notation ofTuring machine.
NU Year 2011
Question Define DFA and NFA. What arc the differences betweenDFA and NFA?
NU Year 2010
Question
NU Year 2010
Question Define regular expression. Write down the rules of regular expression.
NU Year 2010
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.
NU Year 2010
Question Convert the regular expression to an E - NFA(i) (0+ 1)*1 (0+ 1)(ii) (a I b)* obi) (a I h).
NU Year 2010
Question Write an algorithm for minimizing number of states.
NU Year 2010
Question Define symbol, string and alphabet.
NU Year 2010
Question define a context-free-grammar that has only string in L(G) area" h" for11 > f.
NU Year 2010
Question Explain Chomsky Normal form with example
NU Year 2010
Question Define leftmost, rightmost derivation and ambiguity
NU Year 2010
Question Write down an algorithm to remove useless symbols to simplifythe context free grammar.
NU Year 2010
Question Define Pushdown Automaton and explain difference ways ofaccepting language of pushdown automaton
NU Year 2010
Question Explain PDA that accepts{WW" W in (0 + 1)*) by emptystack.
NU Year 2010
Question Explain Turing Machines and ID of Turing Machines.
NU Year 2010
Question Show the computation of Turing Machine for the string 000111using ID.
NU Year 2010
Question Explain Multitape Turing Machine with example
NU Year 2010
Question Define Decidable and Undecidable problems
NU Year 2010
Question Prove theAn odd positive integer n can be written as n = 2k + 1, for someinteger k ≥ 0.
Institute East West University 2013
Question prove the There exist irrational numbers x and y such that x power (y) is rational
Institute Ahsanullah Institute of Information and Communication Technology 2013
Question For every prime number p, prove that √p is irrational.
Institute North South University 2013
Question Let n be a positive integer that is not a perfect square. Prove that √n is irrational.
Institute Tejgaon College 2012
Question Prove by induction that n power(4) − 4n power(2) is divisible by 3, for all integers n ≥ 1.
Institute Tejgaon College 2013
Question Prove that in any set of n + 1 numbers from {1, 2, . . . , 2n}, there are always two numbers that are consecutive.
Institute Shaikh Burhanuddin Post Graduate College 2014
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.
Institute Ahsanullah Institute of Information and Communication Technology 2013
Question Define theThe pumping lemma and nonregular languages
Institute Abudharr Gifari College 2012
Question Proof of Higman’s Theorem
Institute Dhaka College 2014
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.
Institute North South University 2013
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}
Institute East West University 2013
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)∗
Institute East West University 2014
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.
Institute East West University 2014
Question Let  ={a,b}. Draw a DFA that will accept set of strings beginning with a andending with b.
Institute College of Business Science & Technology 2013
Question What is the difference between transition function and extended transition function? What is the purpose of defining extended transition function?
Institute North South University 2015
Question Let  ={0-9,.} Design a DFA that will accept set of both integer numbers and floatnumbers.
Institute East West University 2015
Question What is the definition of a DFA?
Institute Ahsanullah Institute of Information and Communication Technology 2015
Question What is regular expression? (2017,2016,2015,2010)