Some Practice Problems about Finite Automata, Right-Linear Grammars, and Regular Sets

1. True or false: All finite languages are regular. Prove it.
2. Which of the following languages over {0,1}* is/are regular? Prove it.
• The set of strings that have more 0's than 1's (e.g., 110100001).
• The set of strings that, interpreted as binary numbers, are not divisible by seven ( e.g., 111110).
• The set of strings that have some pair of 1's separated by at string that contains at least three 0's (e.g., 01011111100100).
• The set of strings that do not have some pair of 1's separated by at string that contains at least three 0's (e.g., 01011111010000).
• The set { w in {0,1}* | w has an odd number of 0's or else w has at least two 0's and at least two 1's }.

3. Consider the nfsm M = ( { 1, 2, 3 }, { a, b, c }, f, 1, { 1, 3 } ), where
           f ( 1, a ) = { 1, 2 },
           f ( 1, b) = { 2 },
           f ( 1, c ) = { 2, 3 },
           f ( 2, a ) = { },
           f ( 2, b ) = { 1, 3 },
           f ( 2, c) = { 1 },
           f ( 3, a ) = { 3 },
           f ( 3, b ) = { 1, 2 },
           f ( 3, c ) = { 1, 2, 3 }.
• Find a regular expression for the set L(M).
• Is abbacbcab in L(M)?
• Construct deterministic finite automaton, D, such that L(D) = L, by converting M.
• From M, construct a right-linear grammar, G, such that L(G)  = L.
• Add a lambda-move from state 1 to state 3, then repeat the above problems.

4. Find a nfsm, M, such that L(M) is the set denoted by the regular expression
               ( (a+b)*(ab+cba) + (ba)*(a+bc) )*  .
5. In the textbook, do exercises 2.2.1, 2.2.4, 2.2.5, 2.2.6 (pp. 53-55).
6. In the textbook, do exercises 2.3.1, 2.3.2, 2.3.3, 2.3.4 (pp. 66-68).
7. In the textbook, do exercises 2.5.1, 2.5.2, 2.5.3 (p. 80).
8. In the textbook, do exercises 3.1.1, 3.1.2, 3.1.3 part b, 3.1.4, 3.1.5 (pp. 88-89).
9. In the textbook, do exercises 4.1.1, 4.1.2 parts a-f, 4.1.4 (pp. 129-130).
10. In the textbook, do exercises 4.2.2, 4.2.6, 4.2.7, 4.2.11 (pp. 145-148).
11. In the textbook, do exercises 4.3.2, 4.3.3, 4.3.4, and 4.3.5 (pp. 153-154).

---

Revised on 17 October 2009