Skip to content
Tutorials Center
My learning

Topics

Lesson 55 of 59 ยท Practice and Review

Practice: Finite Automata and Regular Languages

Worked practice problems on DFAs, regular expressions, the pumping lemma and Myhill-Nerode, with every solution checked by a Python test harness you can run and extend.

Theory sticks when you solve problems. This lesson collects the types of exercise that appear again and again in courses and exams about finite automata and regular languages, with worked solutions. Even better, every automaton and every regular expression in the solutions is tested by a program against the property it is supposed to recognize, so you can trust them and learn the testing habit that makes automata easy.

Try each problem on paper first, then read the solution and run the code.

Strategy for designing a DFA

  1. Ask what the machine must remember about the prefix read so far. That memory is the set of states.
  2. Write down the possible memory values, then the transition for each symbol.
  3. Mark as accepting the memory values that mean "the string is in the language".
  4. Test on the empty string and on short strings of every kind.

Problems 1 to 3: DFAs

Problem 1. Binary numbers (most significant bit first) divisible by 3. Problem 2. Strings over {0, 1} with at least two 0s and at least two 1s. Problem 3. Strings over {a, b} whose second symbol from the right is a.

Solutions.

  • Problem 1. Remember the remainder mod 3 of the number read so far: states 0, 1, 2. Reading bit b turns the value v into 2v + b, so the new remainder is (2r + b) mod 3. Start and accepting state: 0 (the empty string reads as zero).
  • Problem 2. Remember how many 0s and how many 1s have been seen, but only up to 2 (more makes no difference). States are pairs (zeros, ones) with each in {0, 1, 2}: nine states. Accept (2, 2).
  • Problem 3. Remember the last two symbols (with padding at the start). Four states suffice: the pair of the last two symbols, where "padding" counts as b. Accept pairs whose first symbol is a.
Python Three DFAs checked against the properties they must recognize

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The empty-string convention in Problem 1 is a good example of why testing matters: our DFA accepts the empty string (remainder 0), and we decided that is the intended meaning. Whenever the empty string is ambiguous, state your convention.

Problems 4 to 8: regular expressions

Write a regular expression for each language over {a, b}.

  • 4. Strings with an even number of as.
  • 5. Strings in which no two as are adjacent.
  • 6. Strings that contain the substring aba.
  • 7. Strings that end with ab or ba.
  • 8. Strings of the form a^n b^m where n + m is even.

Solutions.

  • 4. b*(ab*ab*)*. Every a comes in pairs, with any number of bs around them.
  • 5. (b|ab)*(a|ฮต). Each a that is not the very last symbol must be followed by b.
  • 6. (a|b)*aba(a|b)*. Put the required substring between two arbitrary strings.
  • 7. (a|b)*(ab|ba).
  • 8. (aa)*(bb)*|a(aa)*b(bb)*. Either both counts are even, or both odd.
Python Testing regular expressions against predicates

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Whenever you write a regular expression for an exam, test it mentally on the empty string and on strings where the property is "just barely" true and "just barely" false. That is where mistakes hide.

Problems 9 to 11: pumping lemma proofs

Recall the pumping lemma for regular languages: if L is regular, there is a pumping length p such that every string s โˆˆ L with |s| โ‰ฅ p can be written s = xyz with |xy| โ‰ค p, |y| โ‰ฅ 1, and xy^i z โˆˆ L for all i โ‰ฅ 0. To show that a language is not regular you play a game against an imaginary opponent: the opponent chooses p, you choose a string s, the opponent chooses the split, you choose i and exhibit a contradiction.

Problem 9. Show L = { a^n b^n : n โ‰ฅ 0 } is not regular. Take s = a^p b^p. Because |xy| โ‰ค p, the part y consists only of as, and |y| โ‰ฅ 1. Then xy^2 z = a^{p+|y|} b^p has more as than bs, so it is not in L. Contradiction.

Problem 10. Show L = { a^i : i is prime } is not regular. Take s = a^q for a prime q โ‰ฅ p, so y = a^k with 1 โ‰ค k โ‰ค p. Pump with i = q + 1: the length becomes q + qk = q(1 + k), a product of two numbers greater than 1, so it is composite. Contradiction.

Problem 11. Show L = { ww : w โˆˆ {a, b}* } is not regular. Take s = a^p b a^p b. The segment y lies within the first p symbols, so it is all as. Pumping up shifts the position of the first b to the right, so the string is no longer of the form ww. Contradiction.

The pumping lemma can only prove that a language is not regular. Satisfying its conditions does not prove regularity; some non-regular languages can be pumped. For an if-and-only-if test use Myhill-Nerode.

Problem 12: Myhill-Nerode and minimal DFAs

The Myhill-Nerode theorem says: the number of states in the minimal DFA for L equals the number of equivalence classes of strings, where x ~ y when for every suffix z, xz โˆˆ L exactly when yz โˆˆ L. If there are infinitely many classes, L is not regular.

Problem 12. How many states does a minimal DFA need for "the third symbol from the right is a"? Predict, then check with the program: it groups all prefixes up to a length by their behavior on all suffixes up to a length.

Python Counting Myhill-Nerode classes by brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For "the kth symbol from the right is a" the answer is exactly 2^k, the number of ways to fill the last k positions: the exponential gap between an NFA with k+1 states and the smallest equivalent DFA. For a^n b^n the class count keeps increasing as you allow longer prefixes, so there are infinitely many classes and the language is not regular.

More problems to try

  1. Design a DFA for strings over {0, 1} that contain 101 as a substring. Then complement it.
  2. Write a regular expression for binary strings with no 11.
  3. Convert the NFA for "ends in 01" to a DFA by the subset construction and minimize it. Use the toolkit from the DFA project.
  4. Is { a^n b^m : n โ‰  m } regular? (Hint: think about closure under complement and intersection with a*b*.)
  5. Show that regular languages are closed under reversal by reversing every arrow of an NFA and swapping start and accept states.
  6. Use the product construction to design an automaton for "even number of 0s and divisible by 3".

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. For a DFA that checks divisibility by 3 of a binary number read left to right, what is the transition from remainder r on bit b?

    Appending bit b turns the value v into 2v + b, so the remainder becomes (2r + b) mod 3.
  2. 2. In the pumping lemma proof for a^n b^n with s = a^p b^p, why must y consist only of a's?

    The pumping lemma guarantees |xy| <= p, and the first p symbols of s are all a's.
  3. 3. How many states does the minimal DFA for 'the third symbol from the right is a' need?

    The machine must remember the last three symbols, giving 2^3 = 8 distinguishable classes.
  4. 4. Which regular expression describes strings over {a, b} with no two adjacent a's?

    Every a (except possibly the last symbol) must be followed by b, which is what (b|ab)*(a|ฮต) enforces.
  5. 5. A language that satisfies the pumping lemma conditions is

    The pumping lemma is only a necessary condition. Use Myhill-Nerode or an explicit automaton to prove regularity.

Summary

  • Design a DFA by deciding what the machine must remember; the memory values become the states.
  • Test every automaton and regular expression against a predicate on all short strings.
  • Pumping lemma proofs follow a fixed game: pick s, argue where y must lie, pump to break membership.
  • Myhill-Nerode counts the states of the minimal DFA and gives an exact criterion for regularity.

Next: Practice: Grammars and Pushdown Automata