Model Paper-3 | Theory of Computation

B.Tech CSE III Semester Model Paper

Theory Of Computation 

Time:3 Hours		Max Marks:70
Sno.		Questions	Marks
1	a	Construct a DFA which accept a string of a's and b's starts and ends with the same symbol.	2
	b	Construct a FA for  following RE aa* and (ab* + b)	2
	c	Suppose R be any regular expression than write down some identity rule of RE.	2
	d	Create parse tree for E→E + E | E * E | (E) | id and verify id+id*id.	2
	e	Explain about the type of grammar.	2
2	a	Construct a RE to given finite automata using arden's theorem.	5
OR
3	a	Explain about the minimization of Finite Automata with example.
4	a	Minimize the given DFA using tabular method.	5
OR
6	a	Minimize the given DFA using set method.
7	a	What is FA with output.Explain with their formal definition.	5
9	a	Construct a moore machine which print even if number of 0's are even and print odd if number of 0's are odd against input string of 0's and 1's.	5
10	a	Convert the given moore machine to mealy machine.	10
11	a	What is Grammar and the normal form of grammar with example.	10
12	a	Convert the given grammar into chomsky normal form (CNF).     S → aB | bA  , A → bAA | aS | a , B → aBB | bS | b	10
14	a	Explain the complete procedure to remove left recursive grammar with the help of example.	10