Model Paper - 2 | 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 0's and 1's contain 3 consecutive 0's.	2
	b	Construct a FA for following RE  (01)* + 0  and  (0+1)*.	2
	c	Suppose R be any regular expression than write down some identity rule of RE..	2
	d	Define parse tree.Give one example.	2
	e	Explain about the normal form of grammar..	2
2	a	Design a DFA accept a language L{w | w has both an even number of 0's and even number of 1's}	5
OR
3	a	Construct a DFA for given FA with all tuples.
4	a	Convert given FA into DFA with all tuples.	5
OR
6	a	Define regular expression with example.Prove that following.
7	a	Construct a DFA for (01* + 1) with complete tuples.	5
9	a	Construct a DFA for (a+b)*abb with complete tuples.	5
10	a	Consider an automata M1 and M2 are given Suppose R1 ia a R.E which is accepted by M1 and R2 be any R.E which is accepted by M2. Construct an DFA for (R1 U R2).	10
11	a	Explain about Arden's Theorem.Apply in the given example.	10
12	a	Construct a regular expression(R.E) by given finite automata using Arden's theorem.	10
14	a	Construct a regular expression(R.E) by given finite automata using Arden's theorem.	10