CS2303- Theory of Computation

PART-A(2-MARKS)
1 List any four ways of theorem proving.
2 Define Alphabets.
3 Write short notes on Strings.
4 What is the need for finite automata?
5 What is a finite automaton? Give two examples.
6 Define DFA.
7 Explain how DFA process strings.
8 Define transition diagram.
9 Define transition table.
10. Define the language of DFA.
11. Construct a finite automata that accepts {0,1}+
12. Give the DFA accepting the language over the alphabet 0,1 that have the set of all strings ending in 00.
13. Give the DFA accepting the language over the alphabet 0,1 that have the set of all strings with three consecutive 0’s.

14. Give the DFA accepting the language over the alphabet 0,1 that have the set of all strings with 011 as a substring.
15. Give the DFA accepting the language over the alphabet 0,1 that have the set of all strings whose 10
the symbol from the right end is 1.
16. 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.
17. Give the DFA accepting the language over the alphabet 0,1 that have the set of all strings that either begins or end(or both) with 01.
18. 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.
19. Find the language accepted by the DFA given below.
20. Define NFA.
21. Define the language of NFA.
22. Is it true that the language accepted by any NFA is different from the regular language? Justify your Answer.
23. Define ε-NFA.
24. Define ε closure.
25. Find the εclosure for each state from the following automata.