Lab 7 - 09/16 Wednesday


Now that we have introduced languages that are not regular (non-regular? irregular?), a good skill to have is to be able to prove that a language is not regular. There are three main ways to do this:

  1. Closure properties of regular languages.
  2. Myhill-Nerode theorem (necessary and sufficient condition).
  3. Using the Pumping Lemma for regular languages (necessary condition).

Prof. Fleck’s CS173 textbook doesn’t mention necessary/sufficient conditions so here is quick primer: divisibility by 4 is sufficient for a number to be even, but it is not necessary. In contrast, being even is necessary for being divisble by 4, but it is not sufficient. Correspondingly, we say even(x) if div(x,4) and div(x,4) only if even(x).

Closure Properties

We can illustrate the first with a thought exercise. Suppose we have a known nonregular language \(L_{nr}\) and we want conclude something about a language \(L_u\) whose regularity is unknown. If we can show that \(L_{nr}\) arises out of \(L_u\) by applying a regular operation with an regular language, then we can conclude that \(L_u\) is non-regular.

  1. Show that the language: \[ L_u = \left\{ w \in {0,1}^* \mid w \text{ has an equal number of 0s and 1s}\right\}\] is non-regular.

  2. Show that the language: \[ L_u = \left\{ w \in {0,1}^* \mid w \text{ has exactly twice as many 0s as 1s}\right\}\] is non-regular.

Fooling Sets

Recall fooling sets and distinguishability. Two strings \(x, y \in \Sigma^*\) are suffix distinguishable with respect to a given language \(L\) if there is a string \(z\) such that exactly one of \(xz\) and \(yz\) is in \(L\). This means that any DFA that accepts \(L\) must necessarily take \(x\) and \(y\) to different states from its start state. A set of strings \(F\) is a fooling set for \(L\) if pair of strings \(x,y \in F, x \neq y\) are distinguisable. This means that any DFA for \(L\) requires at least \(|F|\) states. To prove non-regularity of a language \(L\) you need to find an infinite fooling set \(F\) for \(L\). Given a language \(L\) try to find a constant size fooling set first and then prove that one of size \(n\) exists for any given \(n\) which is basically the same as finding an infinite fooling set.

We covered Fooling Sets in class but before presenting problems, we also encourage the interested student to read the following supplements to understand that fooling sets arise from a seminal theorem called the Myhill-Nerode theorem (which we may not get to cover in class).

  • [JEMC, Ch. 3.8-3.10] – Prof. Erickson in fact shows how the Myhill-Nerode theorem characterizes minimal DFAs recognizing a regular language.
  • Prof. Chekuri’s Note on Fooling Sets which contains good hints on developing intuition for coming up with fooling sets.

The following problems are about proving non-regularity:

  1. Show that the following language is non-regular: \[\set{0^{2n}1^n \; \mid\; n\ge 0}\]

  2. Show that the following language is non-regular: \[\set{0^m1^n \; \mid \; m\ne 2n}\]

  3. Show that the following language is non-regular: \[\set{0^{2^n} \; \mid \; n\ge 0}\]

  4. Show that the language formed by strings of properly nested parantheses: (), braces: {}, and brackets: [] is non-regular.

Pumping Lemma

We don’t cover the pumping lemma in class, but it is a very useful tool for proving non-regularity. Interested folks can read the following references: