Model Paper- I | Theory of computation

B.Tech CSE III Semester Model Paper

Theory Of Computation 

Time:3 Hours		Max Marks:70
Sno.		Questions	Marks
1	a	What is Finite Automata ? with example.	2
	b	What is the difference beteween NDFA and DFA ?	2
	c	Explain why we use Null move or epsilon move.	2
	d	Define regular expression.Give one example.	2
	e	Difference between kleen closer and positive closer	2
2	a	Define all tuples of given diagram and find whether 011,0111 is accepted or not.	5
OR
3	a	Write down the formal definition of Non deterministic finite automata. If input string is 0100 than check whether it is accepted or not for given diagram.
4	a	Explain about deterministic finite automata (DFA) and write down the condition of DFA.Give one example with all tuples.	5
OR
6	a	Convert the given Non deterministic finite automata to deterministic finite automata.
7	a	Convert the given Non deterministic finite automata to Deterministic finite automata.	5
9	a	Construct a DFA which accept string of 0's and 1's end with substring 00 and write all tuples.	5
10	a	Construct a DFA which accept a string of a's and b's start and end with a and write all tuples.	10
11	a	Construct a DFA which accept a string of a's and b's contains even number of a's followed by odd number of b's and write all tuples.	10
12	a	Construct a DFA which accept number (integer) divisible by 2 or multiple of 2.	10
13	a	Construct a DFA which accept number (integer) divisible by 2 or multiple of 2.	10