1 Select College Department of Computer Science and Technology Formal Language Theory (CSC 471) Worksheet on Regular Languages 1. In figure below, find d*(q0 ,1011) and d*(q1 ,01). 2. For S= {a,b}, construct DFA's that accept the sets consisting of: (a) all strings with exactly one a. (b) all strings with at least one a. (c) all strings with no more than three a's. (d) all strings with at least one a and exactly two bs. (e) all the strings with exactly two as and more than two bs. 3. Show that L= {an : n =4} is regular. 4. (a)Construct a NFA over ={a,b}, where the length is equal to 2. (b)Design a FA that accepts strings containing 010 as a substring. (c)Construct FA that accepts of strings that are multiples of 3 over ={a,b}. (d)Construct a NFA over ={a,b}, where the length is equal to 2. (e)Design a FA with ={0,1} that accepts those strings which starts with 1 and ends with 0. 5. Design an NFA for a language that accepts all strings over {0,1} in which the second last symbol is always 1. Then, convert it to its equivalent DFA. 6. Define primitive regular expressions. 7. Find all strings in L((a + b) b (a + ab)*) of length less than four. 8. Find a regular expression for the set {an b m :( n + m) is even}. 2 9. Give regular expressions for the following languages on S = {a, b, c}. (a) all strings containing any number of as , bs and cs. (b) all strings containing exactly one a. (c) all strings containing no more than three as. (d) all strings that contain at least one occurrence of each symbol in S. (e) all strings whose length is equal to 2. (f )all strings whose length is at least 2. 10. Write regular expressions for the following languages on {0, 1}. (a) all strings starting with 1. (b) all strings ending in 01. (c )all strings starting with 1 and ending in 1. (d) all strings not ending in 01. (e) all strings containing an even number of 0s. (f) all strings having at least two occurrences of the substring 00. (Note that with the usual interpretation of a substring, 000 contains two such occurrences). (g) all strings with at most two occurrences of the substring 00. 11. What languages do the expressions (*)*and a denote? 12. Give an NFA that accepts the language L((a + b)* b(a + bb)*). 13. Define regular grammar. 16. Construct a DFA that accepts the language generated by the grammar: S ? abA, A ? baB, B ? aA|bb. 17. Find a regular grammar that generates the language L (aa* (ab+ a)* ). 3 18.Define the operations of: (a) homomorphism (b) inverse homomorphism (c) right quotient 20. Convert the following finite automata to the left linear grammar. 21. State pumping lemma for regular languages.

Attachments:

Worksheet-on-....pdf