Thursday, October 3, 2013

More pumping lemma stuff

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\}$ ¹
• $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?² 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.³ 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.