Fifth Friday: Finding Further Fantastic Fun from Fabulous FSAs

On Wednesday, we learned about finite state automata (FSAs). An FSA is a finite, labeled, directed graph, whose vertices are called states, and whose edges are labeled with elements of a finite set called an alphabet. At least one vertex is designated a start state, and a subset of the vertices are designated accept states. An FSA accepts a string $x$ if there exists a path labeled with the letters of $x$ that connects the start state to an accept state. An FSA $M$ accepts a language $L$ if $M$ accepts a string $x$ if and only if $x \in L$ .

A deterministic finite automaton (DFA) is an FSA with a unique start state, no two edges with the same label leaving the same vertex, and a label on every edge. A DFA is complete if, for every $s \in S$ , every vertex has an edge leaving it labeled with $s$ . A language is regular if there exists an FSA that accepts it. For any regular language $L$ , there exists a complete DFA that accepts $L$ .

We left off last class with some exercises regarding the closure properties of regular languages – if $L$ and $K$ are regular languages over the alphabet $S$ , show the following are also regular:

$S^* - L$ (here, $^*$ is the Kleene star, meaning $S^*$ is the set of strings consisting of letters from $S$ ). We denote this language $L^{c}$ or $L^{opp}$ .
$L \cup K$
$L \cap K$
$LK$ (the concatenation of $L$ and $K$ , or the set of strings $xy$ where $x \in L$ and $y \in K$ )
$L \cup LL \cup LLL \cup...$

Proof.

(1) If $L$ is regular, there exists a complete DFA $M_L$ that recognizes $L$ . We construct a new complete DFA $M'$ that is identical to $M_L$ , but where any accept state in $M_L$ is a non-accept state in $M'$ , and any non-accept state in $M_L$ is an accept state in $M'$ . Because $M_L$ is complete, any string $s \in S^*$ has a unique corresponding path from the start state to a state in $M_L$ . That path ends at an accept state in $M_L$ if and only if it does not end in an accept state in $M'$ . Therefore, $M'$ accepts the set of strings over $S^*$ that are not accepted by $M_L$ , which corresponds exactly to $S^* - L$ .

(2) If $L$ is regular and $K$ is regular, there exist corresponding FSAs $M_L$ and $M_K$ that recognize $L$ and $K$ . We construct a new FSA $M'$ that consists of $M_L$ , $M_K$ , and a new start state $v$ that has a $-labeled edge to each of the vertices that was a start state in $M_L$ or $M_K$ . Then, $M'$ consists of all strings recognized by $M_L$ or by $M_K$ , so it recognizes $L \cup K$ , meaning $L \cup K$ is regular.

(3) Closure under intersection follows from parts (1) and (2). Observe that:
$L \cap K = L \cup K - [(L \cup K) - L] \cup [(L \cup K) - K]$ . Because regularity is preserved under taking complements and unions, it is also preserved under taking intersections.

(4) Because $L$ and $K$ are regular, there exist FSAs $M_L$ and $M_K$ that accept $L$ and $K$ . Construct a new FSA $M'$ by drawing a $-labeled edge from each accept state of $M_L$ to the start state of $M_K$ , and making them non-accept states. The resulting language will accept any string $x = \ell k$ where $\ell \in L$ and $k \in K$ .

(5) Because $L$ is regular, there exists an FSA $M$ that recognizes $L$ . Draw $-labeled edges from each accept state of $M$ to its start state to get a new machine $M'$ . $M'$ then accepts any string $x^n$ for $n \in \mathbb{N}$ where $x \in L$ . These strings constitute the language $L \cup LL \cup LLL \cup...$ , and $M'$ recognizes it.

The above results give us lots of ways to show that a given language is regular, but how could we show that a language is not regular? For this, we’ll use an argument called the pumping lemma:

Theorem (pumping lemma for regular languages): Let $L$ be a regular language. Then there exists an integer $p \geq 1$ such that, for every string $x$ where $|x| > p$ , there exist strings $u$ , $v$ , $w$ such that:
1) $x = uvw$
2) $uv^i w \in L$ for all $i \in \mathbb{Z}_{\geq 0}$
3) $|u|,|w| < p$

Proof. The proof is an application of the pigeonhole principle. Suppose a language $L$ over $S^*$ is regular. Then there exists an FSA $M$ that accepts $L$ . Consider a string $x \in L$ such that $|x| \geq |V(M)|$ . Consider the path $\gamma_x$ in $M$ whose edges trace out the letters in $x$ . Because $|x| \geq |V(M)|$ , there are at least $|V(M)|$ edges in $\gamma_x$ , so there must be at least $|V(M)|+1$ vertices. By the pigeonhole principle, at least one vertex is visited more than once. Therefore, there is a cycle along $\gamma_x$ . Let $v$ denote the word formed by the edges in this cycle, so $v$ is a substring of $x$ . Let $u$ denote the prefix of $x$ preceding $v$ , and let $w$ denote the suffix of $x$ following $v$ . Thus, $x = uvw$ . It follows that any word $uv^i w$ for $i \in \mathbb{Z}_{\geq 0}$ is also accepted by $M$ , as the paths traced out by $u$ and $w$ remain the same. Moreover, $u$ and $w$ must both be shorter than $|V(M)|$ , which we choose to denote as $p$ . This proves the lemma.

Illustration of the FSA M. When we “pump” v, we always get another word in L.

How can we use the pumping lemma in practice? We’ll use it to show that the language $L = \{ a^n b^n | n \in \mathbb{N} \}$ is not regular.

Proof. We’ll use proof by contradiction. Suppose $L$ is regular, so the pumping lemma holds for some sufficiently large integer $p$ . Consider the string $x = a^n b^n \in L$ for $n \geq p$ . The pumping lemma tells us there exist strings $u$ , $v$ , and $w$ such that $x = uvw$ where $|u|,|w| < p$ . Because $|u|,|w| < p$ , $u$ consists solely of $a$ ‘s, and $v$ consists solely of $b$ ‘s. Moreover, $v = a^\ell b^m$ for $\ell, m>0$ . We contradict condition 2 of the pumping lemma, as for any $i \geq 2$ , $u v^i w \notin L$ .

Because I couldn’t help myself, I’ve outlined another way we can show $\{ a^n b^n | n \in \mathbb{N} \}$ is not regular using the Myhill-Nerode theorem.

Theorem (Myhill-Nerode): Given a language $L$ over the alphabet $A$ , let $_L \sim$ be an equivalence relation on $A^*$ where $x _L\sim y$ if there does not exist $z \in A^*$ such that $xz \in L$ and $yz \notin L$ (or vice-versa). (This relation is sometimes called Nerode congruence). $L$ is regular if and only if $_L \sim$ has a finite number of equivalence classes.

I’ll forego a formal proof of the theorem here, but to get an intuition for why its true, note that (if $L$ is regular) each equivalence class corresponds to a state in a minimum-size complete DFA recognizing $L$ .

We can use the Myhill-Nerode theorem to show that $L = \{ a^n b^n | n \in \mathbb{N} \}$ is not regular.

Proof. Consider the set of strings $\{ a^n | n \in \mathbb{N} \}$ . Each strings $a^k$ has a unique string $b^k$ that can be appended to it to get a string in $L$ . Therefore, each string in $\{ a^n | n \in \mathbb{N} \}$ belongs to a unique equivalence class, so the Nerode congruence for $L$ has an infinite number of equivalence classes. Thus, $L$ is not regular.

At the end of Wednesday’s class, we discussed whether English is a regular language. While at the time I believed the answer was likely yes, I’ve since been convinced otherwise by some super interesting lecture notes from a course at UMass called Mathematical Linguistics, which itself borrowed the argument from the book Mathematical Methods in Linguistics, by Partee, ter Muelen, and Wall (page 480 in the pdf).

Here’s the essence of the argument: earlier, we showed that $\{a^n b^n | n \in \mathbb{N} \}$ is not regular. A nearly identical proof can be used to show that $\{a^n b^{n-1} c | n \in \mathbb{N} \}$ is also not regular. If we replace the letters $a$ , $b$ , and $c$ with strings, the language remains non-regular. In particular, we’ll replace $a$ with a noun (“the dog ”), $b$ with a transitive verb (“chased ”), and $c$ with a non-transitive verb (“got away”). Thus, we’re concerned with the language $L = \{$ (“the dog ”) $^n$ (“chased ”) $^{n-1}$ (“got away”) $| n \in \mathbb{N}\}$ .

I argue that this is a set of grammatically correct strings in the English language. If $n=1$ , then the corresponding string is “the dog got away”, which is a valid English statement. If $n=2$ , then the string is “the dog the dog chased got away” – in other words, the dog (who was being chased by another dog) got away. If $n = 3$ , then we have the string “the dog the dog the dog chased chased got away. This means that the dog (chased by another dog, who was chased by a third dog) got away. If you believe this sort of nesting can go arbitrarily deep, then it follows that $L$ is a subset of all English strings.

Here’s the trick: I will argue that the language $K = \{$ (“the dog ”) $^i$ (“chased ”) $^j$ (“got away”) $| i,j \in \mathbb{N} \}$ is a regular language, recognized by the following FSA:

Let $ENG$ denote the set of grammatically correct English strings. Suppose $ENG$ is regular. Because $ENG$ and $K$ are both regular, it follows that $ENG \cap K$ is regular. Observe that a statement of the form (“the dog ”) $^i$ (“chased ”) $^j$ “got away” only makes grammatical sense if $j = i-1$ . Therefore, $L = ENG \cap K$ . However, we know $L$ is not regular! Thus, English is not a regular language.

Okay, I’ve gotten a bit carried away with formal language theory. Let’s get back to algebra.

Recall the word problem: given a presentation for a group $G = \langle S | R \rangle$ and word $w \in S^*$ , is it true that $w =_G e$ ? We say $G$ has a solvable word problem if there exists an algorithm that correctly answers yes or no for any input $w$ . Can we use FSAs to help us solve word problems for certain groups?

Here are a couple ideas:
1) We design an FSA that recognizes a language that consists of words in some normal form for a group. This could help us to solve the word problem for that group.
2) We define a language Null $= \{ w \in S^* | \pi(w) = e \}$ . If Null is regular, then we can solve the word problem by plugging any word into our FSA for Null.

The first idea is one that we will explore (albeit with some modifications) next week when we talk about automatic groups. What about the second idea?

Unfortunately, it won’t do much for us. This is due to the following theorem.

Theorem: Null( $G$ ) is regular if and only if $G$ is finite.

This means our idea can’t really help us, as we already know that any finite group has solvable word problem.

Proof (of Theorem). We will show implication in both directions.

$( \impliedby )$ Let $G$ be finite. Then let the Cayley graph $\Gamma_{G,S}$ be an FSA. Make $v_e$ be the start state and the only accept state.

$( \implies )$ Assume Null( $G$ ) is regular. Let $M$ be an FSA accepting Null( $G$ ).

We may assume that, for every vertex $v \in V(M)$ , there is a path from $v$ to an accept state in $M$ . To see why, note that if there is no such path, $v$ is a “dead state,” so we may remove $v$ (along with the subgraph that is reachable from $v$ ) to get an FSA that recognizes the same language as $M$ .

Claim: $|G| \leq |V(M)|$ .

Let $w, w'$ be words in $S^*$ such that the paths representing $w$ and $w'$ end at the same vertex $v \in V(M)$ . As mentioned above, we can assume that there is a path from $v$ to an accept state. Let $u$ be the string traced out by this path. Therefore, we have that:

$\pi(wu) = \pi(w'u) = e$
$\pi(w)\pi(u) = \pi(w')\pi(u) = e$
$\pi(w) = \pi(w')$

Therefore, if any two words trace out paths that end at the same state, they represent the same element of $G$ . This implies the above claim, which implies $G$ is finite, as any FSA has a finite vertex set. This concludes the proof.

In case it’s not clear already, I think that regular languages are really cool. They show up in lots of unexpected places (in formal linguistics, they form the base of the Chomsky hierarchy; in computer science, they encode decision problems that can be solved using finite amounts of memory). I’m super excited to see what role they play in geometric group theory.

6 Responses to Fifth Friday: Finding Further Fantastic Fun from Fabulous FSAs

Akash Ganguly says:

October 20, 2022 at 10:58 pm

Sam Hiken this post was very cool. I especially appreciated all the extra facts and links! I wonder if there are any languages that are spoken around the world that are regular?

- Sam Hiken says:
  
  October 21, 2022 at 1:24 am
  
  Akash Ganguly I’m glad you liked the post! From what I can find online, most natural languages seem to permit the sort of “center embedding” that allows us to show they are non-regular.
  Here is a paper about how humans are capable of interpreting this sort of embedding, but tamarin monkeys are not: https://pubmed.ncbi.nlm.nih.gov/14726592/
  And here are multiple people refuting the claims made in the above paper, mostly arguing that humans aren’t very good at recognizing non-regular languages either: http://kochanski.org/gpk/papers/2004/FitchHauser/
  http://itre.cis.upenn.edu/~myl/languagelog/archives/001399.html
  https://link.springer.com/article/10.3758/BF03196377
  
Michaela Polley says:

October 21, 2022 at 7:21 am

Sam, this was a really fun post! I liked the FSA that you drew with the edges labeled with words — it was a great way to get me thinking about regular languages in a new way, but in a way that I already had some grasp on (the English language and grammar rules).

Osip Surdutovich says:

October 21, 2022 at 3:27 pm

Really nice post Sam! I enjoy the style of the pumping lemma and how it gives us so much useful information for the Word Problem. Also, I love your example where you include actual words in the FSA to make your point — nice work!

John Eichelberger says:

October 24, 2022 at 12:01 am

A most delightful post Sam! I really enjoyed getting your insight into more of the things you can do with automata.

On whether spoken languages are regular: I like your example, although it quickly ( $n > 3$ ) approaches unintelligibility for a reader. The technical argument seems sound. It’s not quite the same problem, but I’m just reminded that English has plenty of grammatical sentences that don’t contribute to our ability to communicate (eg. “Colorless green ideas sleep furiously”) and plenty of non-grammatical sentence fragments that are meaningful.(“And now?”)

Shuhang Xue says:

October 24, 2022 at 11:37 pm

Such nice pictures, Sam! You need to let me know how to make those great diagrams.

I absolutely loved your discussion that English is not a regular language through the “dog chasing dogs” instance. For the pumping lemma, Akash suggested that we can use it to prove the last proposition of your post. I want to expand on this thought. Indeed, to prove the statement, we need to show that the null is not regular for infinite groups. We note that any word a^na^{-n} is in the null. Then, for the pumping lemma to work, we have to make sure that u and w have different lengths, where a^na^{-n}=uvw, to create disparities on the sum of exponents for the desired contradiction. However, I am stuck on guaranteeing this to be true. Does anyone have a solution?

Fifth Friday: Finding Further Fantastic Fun from Fabulous FSAs

6 Responses to Fifth Friday: Finding Further Fantastic Fun from Fabulous FSAs

Leave a Reply Cancel reply

Recent Posts

Recent Comments