## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

### 3.5   ADDITIONAL EXERCISES

1. Describe in set-theoretic notation the language of the automaton in 3.1.2.4. Independently, describe set-theoretically the complement {0n 1 : n ≥ 0} and verify that your two answers are equivalent.
2. Construct a FA M over A = {0, 1} such that L(M) = { }
3. Construct a FA M over A = {0, 1} such that L(M) = {0, 1}+, that is, L(M) = A* − { }.
4. Construct a FA that accepts L = {00, 11, 10} over A = {0, 1}.
5. Let Σ = {0}. Which of the following languages over Σ is regular, and why?

(a) {x : |xx| is odd}

(b) {x : |x| is odd}

(c) {x : |xx| is not a prime}

(d) {x : |x| is not a prime}

(e) {x : |x| is a perfect cube}

6. Find a finite automaton that accepts the language over A = {0, 1} that contains precisely the strings that have no three consecutive 0s.
7. Find a finite automaton that accepts the language over A = {0, 1} that contains precisely the strings that end in precisely three consecutive 0s.
8. Find a finite automaton that accepts the language over A = {0, 1} that contains precisely the strings that end in at least three consecutive 0s.
9. Design a FA over {0, 1} that accepts exactly all the strings of length 3k + 1 for some natural number k.E.g., 0, 0110, 0000 are all in. 00, 000, 01101 are not.
10. Build a NFA that accepts precisely all the strings over {0, 1} of length ≥ 5 that ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required