Thursday, October 3, 2013 CC-BY-NC
More pumping lemma stuff

Maintainer: admin

The rest of the assignments (for assignment 1) were returned. Today: more examples for proving irregularity, unary vs binary languages, understanding an arbitrary DFA.

1Proving irregularity, continued

$$L = \{a^n \,\mid\, n \text{ is prime}\}$$

This is clearly not regular. We can prove this using the contrapositive of the pumping lemma, as we did last time.

  • A picks $p$
  • You choose $w = a^n$ where $n \geq p + 2$ is prime
  • A chooses some $y = a^m$ where $1 \leq m \leq p$. Since $w = xyz$, $|xz| = |w| - |y| = n - m$.
  • Now, $|xy^iz| = |xz| + |y| \cdot i = n - m + im = n - m(i-1)$. If you choose $i = n+1$, then $|xy^iz| = n - m(n-1+1) = n-mn = (m+1)n$, which is not prime if neither $n$ nor $m+1$ are 1. Since $n \geq p+2$, and $m \geq 1$, then yes, neither factor is 1. Thus $|xy^iz|$ is not prime, and so $xy^iz \notin L$. $\blacksquare$

1.1Further examples

Left as an exercise for the diligent reader.

  • $L = \{a^n \, \mid \, n \geq 0\}$ 1
  • $L = \{a^{n^2} \,\mid\,n\geq 0\}$

2Regular infinite subsets

We know (from last lecture) that $L = \{a^nb^n \, \mid \, n \geq 0\}$ is not regular. Does it have any infinite regular subsets?2 No, it does not. One way to prove this is to show that there are infinitely many equivalence classes (recall Myhill-Nerode), of the form $[a^n]$ for some $n$. Another way is to use the pumping lemma (the steps are the same as for $\{a^nb^n\,\mid\,n\geq 0\}$).

Consider another language: $\{w\,\mid\,N_a(w) = N_b(w)\}$. We saw last time that this is also not regular. Does this language have any infinite regular subsets? Yes, it does: $(ab)^*$ is one prominent example.

3Unary and binary languages

Suppose $S \subseteq \mathbb{N}$. We define the unary function as follows:

$$\text{unary}(S) = \{w \,\mid\, |w| \in S\}$$

where $\text{unary}(S) \subseteq \{a\}^*$. For example, if $S = \{2, 3, 5\}$, then $\text{unary}(S) = \{aa, aaa, aaaaa\}$.

Similarly, we define binary in the usual way. $\text{binary}(S) \subseteq \{0, 1\}^*$, and $\text{binary}(S) = \{10, 11, 101\}$.

Consider the relationship between binary and unary. Here are two statements:

  • ($\alpha$) If $\text{unary}(S)$ is regular, then so is $\text{binary}(S)$.
  • ($\beta$) If $\text{binary}(S)$ is regular, then so is $\text{unary}(S)$.

One of them is true, the other is false. Since unary is a simpler system than binary, one might expect that ($\alpha$) is true, and $(\beta)$ is false. Indeed, this is correct: a counterexample to ($\beta$) is $10^*$, which is obviously regular as it is a regular expression; however, the corresponding unary language, $\{a^{2^n} \,\mid\,n \geq 0\}$, is not regular, as we showed last class.

Let's now prove that ($\alpha$) is true. First, consider the structure of the DFA for any regular language over a 1-letter alphabet. Since there's only one letter in the alphabet, there can only be 1 transition (at most) out of any state. So there's only one possible path to follow, and there is at most one loop-around (possibly none, if the language is finite), and some of the states are accept states.

At this point, we introduce a new term: an ultimately periodic set $U \subseteq \mathbb N$ is a set defined by 2 positive integers, $p$ and $n_0$, such that $\forall n \geq n_0$, if $n \in U$, then $n+p\in U$ (so $p$ is the period).

The fact that the only possible path loops back around at some point means that the lengths of words in any regular language over a 1-letter alphabet form an ultimately periodic set.3 Then $\text{binary}(S)$ will be the binary encoding of an ultimately periodic set, which can also be thought of as the union of a finite set and a periodic set. It should be clear that we can construct a DFA over a binary alphabet for any such language.

4Understanding an arbitrary DFA

Suppose you're given an arbitrary DFA $M$ with $n$ states. We can prove the following:

The set of words accepted by $M$ is non-empty $\iff$ $M$ accepts a word of length $\leq n$.

(Proof omitted)

The set of words accepted by $M$ is infinite $\iff$ $M$ acccepts a word of length $l$, where $n < l < 2n$.

(Proof left as an exercise)

So if we wish to determine what $M$ accepts (treating it as a black box), we could just try every word up to length $n$. If no such words are accepted, then we know that $M$ doesn't accept anything - it recognises the empty language.

4.1Transition graphs

Given the transition graph for a DFA, we can check if the machine accepts:

  • The empty language: Check reachability (BFS/DFS). If no accept states are reachable, then it accepts the empty language.
  • An infinite language: Test for cycles, reachability, and accept states.
  • Everything: Check if all reachable states are accept states.
  1. This seems regular to me, as it's just a*. Is there a typo? 

  2. All finite subsets are regular, so we turn our attention to the infinite subsets. 

  3. If there are no loops, then the language is finite, and so the statement is still true, it's just that $n_0$ can be some number $\geq$ the length of the longest word, so that the periodic part is empty.