CS2303- Theory of Computation

PART-A

1 Define Regular expression. Give an example.
2 What are the operators of RE.
3 Write short notes on precedence of RE operators.Write Regular Expression for the language that have the set of strings over {a,b,c} containing at least one a and at least one b.
4 Write Regular Expression for the language that have the set of all strings of 0’s 5 and 1’s whose 10
the symbol from the right end is 1.
6 Write Regular Expression for the language that has the set of all strings of 0’s and 1’s with at most one pair of consecutive 1’s.
7 Write Regular Expression for the language that have the set of all strings of 0’s
8 and 1’s such that every pair of adjacent 0’s appears before any pair of adjacent 9 1’s.
10 Write Regular Expression for the language that have the set of all strings of 0’s and 1’s whose no of 0’s is divisible by 5.
11 Write Regular Expression for the language that has the set of all strings of 0’s and 1’s not containing 101 as a substring.
12 Write Regular Expression for the language that have theset of all strings of 0’s and 1’s such that no prefix has two more 0’s than 1’s, not two more 1’s than 0’s.
13.Write Regular Expression for the language that have the set of all strings of 0’s and 1’s whose no of 0’s is divisible by 5 and no of 1’s is even.

14. Give English descriptions of the languages of the regular expression (1+ ε)(00*1)*0*.
15. Give English descriptions of the languages of the regular expression (0*1*)*000(0+1)*.
16. Give English descriptions of the languages of the regular expression (0+10)*1*.
17. Convert the following RE to ε-NFA.01*.
18. State the pumping lemma for Regular languages.
19. What are the application of pumping language?
20. State the closure properties of Regular language.
21. Prove that if L and M are regular languages then so is LUM.
22. What do you mean by Homomorphism? Suppose H is the homomorphism from the alphabets {0,1,2} to the alphabets {a,b} defined by h(0)=a h(1)=ab h(2)=ba. What is h(0120) and h(21120).
23. Suppose H is the homomorphism from the alphabets {0,1,2} to the alphabets {a,b} defined by h(0)=a h(1)=ab h(2)=ba. If L is the language L(01*2) what is h(L).
24. Let R be any set of regular languages is U Riregular?Prove it.
25. Show that the compliment of regular language is also regular.
26 . What is meant by equivalent states in DFA.