Important Questions - Theory of Computation | Theory of Computation Important Questions

1. Define Alphabet and symbol with example.
2. Define state, transition and state transition diagram with a suitable example.
3. Define a transition system with an example.
4. What is an automaton?
5. What is Finite Automata? Explain with block diagram.
6. What are the components of a Finite Automata.
7. Define Finite Automata.
8. Explain when is a language accepted by a finite automata.
9. Define DFA. Mention the types of Finite Automata.
10. Mention five differences between DFA and NFA.
11. What is trap state? Explain with a simple example.
12. Define DFA with mathematical representation.
13. Distinguish between DFA and NDFA.
14. Write down the definition for NDFA with a proper example.
15. Construct a DFA which accept string of 0’s and 1’s does not contain (101) as a substring.
16. What is a Moore machine?
17. State the difference between a Mealy machine and a Moore machine.
18.Define Mealy machine and Moore machine.
19. Write down the procedure for transforming a Mealy machine into Moore machine with an example.
20. Construct a Mealy machine equivalent to the Moore machine given below :

Present State	Next State		Output
	q=0	q=1
q0	q1	q2	1
q1	q3	q2	0
q2	q2	q1	1
q3	q0	q3	1

 

21. Consider the Moore machine described by the transition table given below.

 

Present State	Next State		Output
	q=0	q=1
q1	q1	q2	0
q2	q1	q3	0
q3	q1	q3	1

 

Construct the corresponding Mealy Machine.

22. Define Regular Expression.
23. Explain the various applications of Regular expressions.
24. State Arden’s theorem.
25. Construct a transition system to the regular expression (ab + c*)* b
26. Construct the finite automation equivalent to the regular expression

(0+1)*(00+11)(0+1)*

27. Explain Arden’s theorem.
28. Differentiate between Context free and Context Sensitive grammar.

29. Short notes:

a. Closure properties
b. Pumping lemma for CFL
c. Pushdown automata (PDA)

30. What is context free language? Explain the left most and right most derivation of context free language with an example.

31. Explain the different types of grammar according to Chomsky hierarchy. Also give example of each one of them.

32. Write short notes on:

a. Pumping lemma

b. Algebra of regular expression

c. Constructing of Turing machine.