O'Reilly logo

Theory of Computation by George Tourlakis

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

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) = {images}
  3. Construct a FA M over A = {0, 1} such that L(M) = {0, 1}+, that is, L(M) = A* − {images}.
  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.

Start Free Trial

No credit card required