CS2303 Theory of Computation Question Bank : dmice.ac.in
Name of the College : DMI College OF Engineering
Subject : Theory of Computation
Website : dmice.ac.in
Document type : Question Bank
Download Theory of Computation Model Question Paper : https://www.pdfquestion.in/uploads/dmice.ac.in/1340-CS2303.doc
DMI Theory of Computation Question Bank
CS2303 Theory of Computation :
UNIT – I
AUTOMATA :
PART-A : (2-MARKS)
1. Define inductive proof. (Nov/Dec 2010)
2. State the differences between NFA and DFA. (Nov/Dec 2011)
3. What is the need for finite automata?
Related : DMI College OF Engineering CS6304 Analog & Digital Communication Question Bank : www.pdfquestion.in/379.html
4. What is a finite automaton? Give two examples. (Nov/Dec 2012)
5. Define DFA.
6. Explain how DFA process strings.
7. Define transition diagram. (Nov/Dec 2012)
8. Define transition table.
9. State the Principle of induction. (Nov/Dec 2012)
10. Construct a finite automata that accepts {0,1}+.
11. Give the DFA accepting the language over the alphabet 0,1 that have the set of all strings ending in 00. (Nov/Dec 2010, 2012)
12. Give the DFA accepting the language over the alphabet 0,1 that have the set of all strings with three consecutive 0’s.
13. Give the DFA accepting the language over the alphabet 0,1 that have the set of all strings with 110 as a substring. (Nov/Dec 2011)
14. Give the DFA accepting the language over the alphabet 0,1 that have the set of all strings whose 10th symbol from the right end is 1.
15. Draw the transition diagram for an identifier. (Nov/Dec2013)
16. What is structural induction (Nov/Dec 2011)
17. Give the DFA accepting the language over the alphabet 0,1 that have the set of all strings such that each block of 5 consecutive symbol contains at least two 0’s.
18. Give the DFA accepting the language over the alphabet 0,1 that have the set of all strings that either begins with 0 and ending with 1. (Nov/Dec 2012)
19. Give the DFA accepting the language over the alphabet 0,1 that have the set of all strings such that the no of zero’s is divisible by 5 and the no of 1’s is divisible by 3.
20. Define NFA. (Nov/Dec 2013)
UNIT – II
REGULAR EXPRESSIONS AND LANGUAGES :
PART-A :
1. Define Regular expression. Give an example.
2. Differentiate Regular Expression and Regular Language. (Nov/Dec 2012)
3. Construct NFA equivalent to the regular expression (0+1)01
4. Is the set of strings over the alphabet {0} of the form on where n is not a prime is regular? Prove or disprove. (Nov/Dec 2011)
5. State Ardens Theorem
6. State the pumping lemma for Regular languages. (Nov/Dec 2010,2013)
7. What are the operations of Regular Expressions.
8. Write the precedence of RE operators.
9. Construct the NFA for the Regular Expression aa*/bb*
10. State the applications of Pumping Lemma.
11. Show that L={ap /p is a prime} is not regular.
12. State the closure properties of Regular language
13. Construct an NFA equivalent to the regular expression (0+1)* (00+11)(0+1)*
14. What is a dead state?
PART-B :
1. Using Pumping Lemma for the regular sets, prove that the language L = {am bn / m>n } is not regular.
2. State and explain the conversion DFA into Regular Expression using Ardens Theorem Illustrate with an example.
3. A) Prove any two Closure propertiesof regular sets.
b) Construct a minimized DFA that can be derived from the following regular expression 0*(01)(0/111)*
4. Convert the following NFA into a regular expression
5. Using pumping Lemma for regular sets prove that the language
L = {0m 1n 0m+n / m=1 and n=1 } is not regular.
6. If L= L(A) for some DFA A, then there is a regular expression R sucvh that L = L(R).
7. Construct a NFA for the regular expression (a/b)* abb and draw its equivalent DFA.
8. Prove that Every language defined by a Regular Expression is also defined by Finite Automata.
9. Convert the following to a regular expression
10. Construct minimized DFA for the following table.
Can you help in solving the following question
Give a dfa that accept the set of strings whose tenth symbol from the right end is 1