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 if there exists a path labeled with the letters of that connects the start state to an accept state. An FSA accepts a language if accepts a string if and only if .

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 , every vertex has an edge leaving it labeled with . A language is *regular* if there exists an FSA that accepts it. For any regular language , there exists a complete DFA that accepts .

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

- (here, is the Kleene star, meaning is the set of strings consisting of letters from ). We denote this language or .
- (the
*concatenation*of and , or the set of strings where and )

*Proof*.

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

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

(3) Closure under intersection follows from parts (1) and (2). Observe that:

. Because regularity is preserved under taking complements and unions, it is also preserved under taking intersections.

(4) Because and are regular, there exist FSAs and that accept and . Construct a new FSA by drawing a $-labeled edge from each accept state of to the start state of , and making them non-accept states. The resulting language will accept any string where and .

(5) Because is regular, there exists an FSA that recognizes . Draw $-labeled edges from each accept state of to its start state to get a new machine . then accepts any string for where . These strings constitute the language , and 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 be a regular language. Then there exists an integer such that, for every string where , there exist strings , , such that:

1)

2) for all

3)

*Proof.* The proof is an application of the pigeonhole principle. Suppose a language over is regular. Then there exists an FSA that accepts . Consider a string such that . Consider the path in whose edges trace out the letters in . Because , there are at least edges in , so there must be at least vertices. By the pigeonhole principle, at least one vertex is visited more than once. Therefore, there is a cycle along . Let denote the word formed by the edges in this cycle, so is a substring of . Let denote the prefix of preceding , and let denote the suffix of following . Thus, . It follows that any word for is *also* accepted by , as the paths traced out by and remain the same. Moreover, and must both be shorter than , which we choose to denote as . This proves the lemma.

How can we use the pumping lemma in practice? We’ll use it to show that the language is not regular.

*Proof*. We’ll use proof by contradiction. Suppose is regular, so the pumping lemma holds for some sufficiently large integer . Consider the string for . The pumping lemma tells us there exist strings , , and such that where . Because , consists solely of ‘s, and consists solely of ‘s. Moreover, for . We contradict condition 2 of the pumping lemma, as for any , .

Because I couldn’t help myself, I’ve outlined another way we can show is not regular using the *Myhill-Nerode theorem*.

**Theorem (Myhill-Nerode):** Given a language over the alphabet , let be an equivalence relation on where if there does not exist such that and (or vice-versa). (This relation is sometimes called *Nerode congruence*). is regular if and only if 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 is regular) each equivalence class corresponds to a state in a minimum-size complete DFA recognizing .

We can use the Myhill-Nerode theorem to show that is not regular.

*Proof*. Consider the set of strings . Each strings has a unique string that can be appended to it to get a string in . Therefore, each string in belongs to a unique equivalence class, so the Nerode congruence for has an infinite number of equivalence classes. Thus, 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 is not regular. A nearly identical proof can be used to show that is also not regular. If we replace the letters , , and with strings, the language remains non-regular. In particular, we’ll replace with a noun (“the dog ”), with a transitive verb (“chased ”), and with a non-transitive verb (“got away”). Thus, we’re concerned with the language (“the dog ”)(“chased ”)(“got away”) .

I argue that this is a set of grammatically correct strings in the English language. If , then the corresponding string is “the dog got away”, which is a valid English statement. If , 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 , 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 is a subset of all English strings.

Here’s the trick: I will argue that the language (“the dog ”)(“chased ”)(“got away”) is a regular language, recognized by the following FSA:

Let denote the set of grammatically correct English strings. Suppose is regular. Because and are both regular, it follows that is regular. Observe that a statement of the form (“the dog ”)(“chased ”)“got away” only makes grammatical sense if . Therefore, . However, we know 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 and word , is it true that ? We say has a solvable word problem if there exists an algorithm that correctly answers yes or no for any input . 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 . 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() is regular if and only if 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.

Let be finite. Then let the Cayley graph be an FSA. Make be the start state and the only accept state.

Assume Null() is regular. Let be an FSA accepting Null().

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

**Claim:** .

Let be words in such that the paths representing and end at the same vertex . As mentioned above, we can assume that there is a path from to an accept state. Let be the string traced out by this path. Therefore, we have that:

Therefore, if any two words trace out paths that end at the same state, they represent the same element of . This implies the above claim, which implies 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.

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?

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

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).

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!

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 () 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?”)

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?