# An introduction to finite automata theory

Nabarun Deka

Indian Institute of Science, CV Raman Road, Bengaluru 560012

## Abstract

In this report, we begin by familiarising ourselves with the theory of finite automata. We study a formal definition of finite automata and the notion of languages being recognized by them. We then look at the concept of 'Nondeterminism', formalise a 'Nondeterministic' finite automata and prove the equivalence of 'Deterministic' and 'Nondeterministic' finite automaton. We then study the problem of trying to describe the languages recognized by finite automata leading to defining 'Regular expressions' and then prove the equivalence of regular expressions and finite Automata. We also look at the problem of constructing minimal finite automata for a given language and study the 'Myhill-Nerode Relations' and the 'Myhill-Nerode' Theorem. We then look at a necessary condition for a language to be recognizable by a finite automaton through the 'Pumping Lemma'. With a familiarity of Finite Automata, we look at a specific problem. We look at the question of defining finite automata that accepts infinite strings as input. We study Büchi's construction of automata on infinite words. Through an example, we study the non-equivalence of 'deterministic' and 'non-deterministic' Büchi automata. We study the characterisation of languages recognized by Büchi automata. We then look at the 'monadic second order logic of one successor', abbreviated as S1S and look at some examples of formulas in S1S. Finally, we study the satisfiability problem in S1S, and Büchi's solution using Büchi automata

Keywords: deterministic finite automata, non-deterministic finite automata, regular expressions, Myhill-Nerode theorem, pumping lemma, Büchi automata

## Abbreviations

The following abbreviations will be used in this report

Abbreviations
 DFA Deterministic Finite Automata NFA Non-Deterministic Finite Automata S1S Monadic second order logic of one successor MN Myhill-Nerode

## Notation

Small letters a,b,c will be used to denote letters of an alphabet.

Small letters u,v,w will be used to denote finite length words.

Greek letters α,β,γ will be used to denote infinite length words.

Capital letters A,B,C will be used to denote Languages

The following report is written by Nabarun Deka, Registration Number: MATS384 as part of the IAS Summer Fellowship Program 2019, under the guidance of Dr. Aiswarya Cyriac, CMI.

## <br /><!--<br /> /* Font Definitions */<br /> @font-face<br /> {font-family:Calibri;<br /> panose-1:2 15 5 2 2 2 4 3 2 4;<br /> mso-font-charset:0;<br /> mso-generic-font-family:swiss;<br /> mso-font-pitch:variable;<br /> mso-font-signature:-536870145 1073786111 1 0 415 0;}<br /> /* Style Definitions */<br /> p.MsoNormal, li.MsoNormal, div.MsoNormal<br /> {mso-style-unhide:no;<br /> mso-style-qformat:yes;<br /> mso-style-parent:"";<br /> margin-top:0cm;<br /> margin-right:0cm;<br /> margin-bottom:10.0pt;<br /> margin-left:0cm;<br /> line-height:115%;<br /> mso-pagination:widow-orphan;<br /> font-size:11.0pt;<br /> font-family:"Calibri","sans-serif";<br /> mso-ascii-font-family:Calibri;<br /> mso-ascii-theme-font:minor-latin;<br /> mso-fareast-font-family:Calibri;<br /> mso-fareast-theme-font:minor-latin;<br /> mso-hansi-font-family:Calibri;<br /> mso-hansi-theme-font:minor-latin;<br /> mso-bidi-font-family:"Times New Roman";<br /> mso-bidi-theme-font:minor-bidi;<br /> mso-fareast-language:EN-US;}<br />p.abunit, li.abunit, div.abunit<br /> {mso-style-name:abunit;<br /> mso-style-unhide:no;<br /> mso-margin-top-alt:auto;<br /> margin-right:0cm;<br /> mso-margin-bottom-alt:auto;<br /> margin-left:0cm;<br /> mso-pagination:widow-orphan;<br /> font-size:12.0pt;<br /> font-family:"Times New Roman","serif";<br /> mso-fareast-font-family:"Times New Roman";}<br />span.msoIns<br /> {mso-style-type:export-only;<br /> mso-style-name:"";<br /> text-decoration:underline;<br /> text-underline:single;<br /> color:teal;}<br />.MsoChpDefault<br /> {mso-style-type:export-only;<br /> mso-default-props:yes;<br /> font-family:"Calibri","sans-serif";<br /> mso-ascii-font-family:Calibri;<br /> mso-ascii-theme-font:minor-latin;<br /> mso-fareast-font-family:Calibri;<br /> mso-fareast-theme-font:minor-latin;<br /> mso-hansi-font-family:Calibri;<br /> mso-hansi-theme-font:minor-latin;<br /> mso-bidi-font-family:"Times New Roman";<br /> mso-bidi-theme-font:minor-bidi;<br /> mso-fareast-language:EN-US;}<br />.MsoPapDefault<br /> {mso-style-type:export-only;<br /> margin-bottom:10.0pt;<br /> line-height:115%;}<br />@page WordSection1<br /> {size:612.0pt 792.0pt;<br /> margin:72.0pt 72.0pt 72.0pt 72.0pt;<br /> mso-header-margin:36.0pt;<br /> mso-footer-margin:36.0pt;<br /> mso-paper-source:0;}<br />div.WordSection1<br /> {page:WordSection1;}<br />--><br />FINITE AUTOMATA: A FORMAL DEFINITION

A Finite Automata is defined as a quintuple $(Q, \Sigma, \delta, q_{0}, F)$where :

1. $Q$ is a finite set called the set of states

2. $\Sigma$ is a finite set called the Alphabet

3. $\delta : Q \times \Sigma \rightarrow Q$is a function called the Transition Function

4. $q_{0} \in Q$ is a state called the Initial State

5. $F \subseteq Q$is called the set of Accept States

The input to a Finite Automaton $(Q, \Sigma, \delta, q_{0}, F)$ are words from the alphabet $\Sigma$. A Finite Automaton always begins in the initial state. As it reads a word (call it $w$), it moves from one state to another as given by the transition function. The state of the automaton after reading the entire input is called the final state. If the final state is an accept state, we say that the automaton accepts the word $w$. The set of all words accepted by an automaton is said to be the Language recognized by the automaton. We formalise this notion of acceptance of a word as follows: Let $M = (Q, \Sigma, \delta, q_{0}, F)$ be a finite automaton, and let $w = a_1a_2\dots a_n$ be a word where each $a_i$belongs to the alphabet $\Sigma$. Then, $M$ accepts $w$ if there exist a sequence of states $r_0,r_1,\dots,r_n$ in $Q$ (such a sequence of states is called an accepting run of the word $w$ on the automaton $M$) such that:

1. $r_0 = q_0$

2. $r_{i+1} = \delta(r_i,a_{i+1})$ for $i = 0,1,\dots,n-1$

3. $r_n \in F$

It is easier to represent Finite Automata pictorially than as a quintuple. We shall look at this through a few examples.

Example 1: Consider the language, $L_1$, of all even numbers expressed in the binary number system. We will build a finite state automaton that will recognize this language (It reads the string from most significant digit to least significant one). We observe that all even numbers end with the digit 0 in the binary number system, while all odd numbers end with the digit 1. Thus, we can build an automaton that recognizes this language by using two states to keep track of the last digit read by the automaton. As a convention, we will take the empty string to be an even number. The automaton is shown in the figure below.

Automaton that recognizes  $L_1$

Example 2: Consider the language, $L_2$, over the alphabet $\{0,1\}$ that contains all strings that contain the substring $001$. The idea behind this construction is to check for the substring $001$ while reading the string, and then accepting if we find it. The automaton that accepts this language is shown below.

Automaton that recognizes  $L_2$

A language, $L$, is said to be a Regular Language if it is recognized by some finite automaton.

## NON-DETERMINISM<br /><!--<br /> /* Font Definitions */<br /> @font-face<br /> {font-family:Calibri;<br /> panose-1:2 15 5 2 2 2 4 3 2 4;<br /> mso-font-charset:0;<br /> mso-generic-font-family:swiss;<br /> mso-font-pitch:variable;<br /> mso-font-signature:-536870145 1073786111 1 0 415 0;}<br /> /* Style Definitions */<br /> p.MsoNormal, li.MsoNormal, div.MsoNormal<br /> {mso-style-unhide:no;<br /> mso-style-qformat:yes;<br /> mso-style-parent:"";<br /> margin-top:0cm;<br /> margin-right:0cm;<br /> margin-bottom:10.0pt;<br /> margin-left:0cm;<br /> line-height:115%;<br /> mso-pagination:widow-orphan;<br /> font-size:11.0pt;<br /> font-family:"Calibri","sans-serif";<br /> mso-ascii-font-family:Calibri;<br /> mso-ascii-theme-font:minor-latin;<br /> mso-fareast-font-family:Calibri;<br /> mso-fareast-theme-font:minor-latin;<br /> mso-hansi-font-family:Calibri;<br /> mso-hansi-theme-font:minor-latin;<br /> mso-bidi-font-family:"Times New Roman";<br /> mso-bidi-theme-font:minor-bidi;<br /> mso-fareast-language:EN-US;}<br />p.abunit, li.abunit, div.abunit<br /> {mso-style-name:abunit;<br /> mso-style-unhide:no;<br /> mso-margin-top-alt:auto;<br /> margin-right:0cm;<br /> mso-margin-bottom-alt:auto;<br /> margin-left:0cm;<br /> mso-pagination:widow-orphan;<br /> font-size:12.0pt;<br /> font-family:"Times New Roman","serif";<br /> mso-fareast-font-family:"Times New Roman";}<br />span.msoIns<br /> {mso-style-type:export-only;<br /> mso-style-name:"";<br /> text-decoration:underline;<br /> text-underline:single;<br /> color:teal;}<br />.MsoChpDefault<br /> {mso-style-type:export-only;<br /> mso-default-props:yes;<br /> font-family:"Calibri","sans-serif";<br /> mso-ascii-font-family:Calibri;<br /> mso-ascii-theme-font:minor-latin;<br /> mso-fareast-font-family:Calibri;<br /> mso-fareast-theme-font:minor-latin;<br /> mso-hansi-font-family:Calibri;<br /> mso-hansi-theme-font:minor-latin;<br /> mso-bidi-font-family:"Times New Roman";<br /> mso-bidi-theme-font:minor-bidi;<br /> mso-fareast-language:EN-US;}<br />.MsoPapDefault<br /> {mso-style-type:export-only;<br /> margin-bottom:10.0pt;<br /> line-height:115%;}<br />@page WordSection1<br /> {size:612.0pt 792.0pt;<br /> margin:72.0pt 72.0pt 72.0pt 72.0pt;<br /> mso-header-margin:36.0pt;<br /> mso-footer-margin:36.0pt;<br /> mso-paper-source:0;}<br />div.WordSection1<br /> {page:WordSection1;}<br />--><br />

Observe that, given a word $w$, the automaton given in Section 1 follows a unique run while reading the word. An automaton that has a unique run on a word is called a deterministic automaton. We can also have automatons that have multiple runs on a given word. Such automata can be constructed by giving multiple transitions from a state on a given input. In addition to this, nondeterministic finite automata also have empty transitions (denoted by $\epsilon$). An empty transition is one where the automaton can make a transition from one state to another without reading any input. Formally, a nondeteministic finite automaton is defined as a quintuple $(Q,\Sigma,\Delta,q_0,F)$ where

1. $Q$ is the set of states

2. $\Sigma$ is the Alphabet

3. $\Delta \subseteq Q \times \Sigma \cup \{\epsilon\} \times Q$is a relation called the Transition Relation

4. $q_{0} \in Q$ is a state called the Initial State

5. $F \subseteq Q$is called the set of Accept States

Observe that a NFA has a transition relation instead of a function i.e given a state $q$ and input letter $a$, the machine can go to state $q'$ iff $(q,a,q') \in \Delta$. This relation introduces the non-determinism in the machine. Similar to a DFA, we define an accepting run of a word $w = a_1a_2\dots a_n$ on a NFA as a sequence of states $r_0,r_1,\dots,r_m$ where $m \geq n$ (the run can be much larger than the length of the input because of empty transitions) such that

1. $r_0 = q_0$

2. $(r_i,b_{i+1},r_{i+1}) \in \Delta$ for $i = 0,1,\dots,m-1$

3. $b_1 b_2 \cdots b_m = a_1 a_2 \cdots a_n = w$

4. $r_m \in F$

We say that a NFA accepts a word $w$ if there exists atleast one accepting run of $w$ i.e. atleast one run ends on an accept state. Note that, if at any point a run encounters a state-letter pair that has no defined transition, the run ends there and becomes invalid (because it hasnt read the complete input).

Example 3: Consider the language $L_3$ of all strings over $\{0,1\}$ that have a $1$ at the third position from the end of the string. We can construct a NFA to accept this language by guessing that each $1$ we encounter is the third one from the end, and then checking whether this is true. The automaton that recognizes this language is given below

Automaton that accepts  $L_3$

## Equivalence of Deterministic and Non-deterministic Automata

Since Non-deterministic automata are able to simulate multiple runs simultaneously, one might expect them to be more powerful than Deterministic Automata, i.e. NFA can recognize languages that cannot be recognized by DFA. Surprisingly, this turns out to be false. We have the following theorem:

Theorem: Every NFA has an equivalent DFA

Proof: Let $N = (Q,\Sigma,\Delta, q_0,F)$ be a NFA. We construct a DFA, $M$, that is equivalent to $N$as follows :

$M = (Q',\Sigma,\delta,q_0',F')$ where

​1. $Q' = P(Q)$ , the set of all subsets of $Q$

2. To define the transition function, we first define $\delta'(q,a)$ as the set of all states reachable from $q$ on the letter $a$ in the NFA i.e $\delta'(q,a) = \{q' \in Q \mid (q,a,q') \in \Delta\}$. Now we define the transition function for $M$ as

$\delta(R,a) = \bigcup_{q \in R} \delta'(q,a)$

3. The start state is the state corresponding to the singleton set $\{q_0\}$

4. The set of final states consists of all the subsets of $Q$that contain atleast one final state from $F$ i.e $F' = \{R \in P(Q) \mid R \cap F \neq \phi \}$

​The machine $M$ keeps track of all the states the NFA is in after reading the input. Hence, if after reading the input $M$ is in a state from $F'$, then there was some run in $N$ that ended in a final state, and hence, the input is accepted by $N$. It is easy to see that these two automata are equivalent.

## REGULAR EXPRESSIONS

We now try to give a characterisation of the regular languages. For this purpose, we define three operations on languages. Let $A$ and $B$ be two languages. We define :

1. Union : $A \cup B = \{x \mid x \in A or x \in B \}$

2. Concatenation : $AB = \{xy \mid x \in A and y\in B \}$

3. Iteration : $A^* = \{ x_1x_2\dots x_k \mid k \geq 0; x_i \in A \forall 1 \leq i \leq k \}$ (Note that this also contains the empty string)

Now, we define regular expressions inductively as follows:

1. The expression $a$ is a regular expression ( $a$ is a letter of some alphabet $\Sigma$)

2. $\epsilon$ which denotes the empty string, is a regular expression

3. $\emptyset$which denotes the empty language, is a regular expression

4. If $L_1$ and $L_2$ are regular expressions, then

4.1 $L_1 \cup L_2$ is a regular expression

4.2 $L_1L_2$ is a regular expression

4.2 $L_1^*$ is a regular expression

Examples :

1. $(0 \cup 1)^*$ is a regular expression that describes the language of all strings over the alphabet $\{0,1\}$

2. $a(a \cup b)^*b$ is a regular expression that describes all strings starting with an $a$ and ending with a $b$

Now, we will prove that regular languages can be characterised using regular expressions. This includes two parts.

## Regular Expressions describe Regular Languages

Theorem : If $R$ is a regular expression, then, it describes a Regular Language

Proof : We prove this by induction on the structure of Regular Expressions. The base cases are the singleton letter, the empty string, and the null language.

1. Singleton letter : The expression $R = a$ describes the language consisting of the sinlge letter string $a$ i.e $L(R) = \{a\}$. This language is regular because it can be recognized by the following two state automaton

2. Empty String : The expression $R= \epsilon$ describes the language consisting of only the empty string i.e $L(R) = \{\epsilon\}$. This is also a regular language as it can be recognized by the following one state automaton

3. Null language: The expression $R = \emptyset$describes the empty language, i.e the language that has no strings. This language is also regular as it can be recognized by the following single state automaton

This proves the base cases. Now, for the inductive step, we show that regular languages are closed under the regular operations, i.e. union, concatenation and iteration of regular languages are also regular.

Let $R_1$ and $R_2$ be regular expressions and let their corresponding regular languages be $L_1$ and $L_2$respectively (this is true from the induction hypothesis). Let the automata recognizing $L_1$ and $L_2$ be $M_1 = (Q_1, \Sigma_1, \delta_1, q_1, F_1)$ and $M_2 = (Q_2, \Sigma_2, \delta_2, q_2, F_2)$ respectively.

1. Union: We construct a NFA that recognizes the union of these two languages by creating a new start state that has empty transitions to the start states of both $M_1$ and $M_2$. We keep $M_1$ and $M_2$ as they are, and make the set of final states the union of their final states. This NFA runs the word on both $M_1$ and $M_2$ simultaneously, and accepts it if it reaches an accept state on any one of them. Hence, it accepts the union of the two languages. Thus, we proved that regular languages are closed under union.

2. Concatenation: We construct a NFA that recognizes $L_1L_2$ by taking $M_1$ and putting empty transitions from the final states of $M_1$ to the start states of $M_2$. The start state of this new NFA is the start state of $M_1$ and the final states are the final states of $M_2$. It is easy to see that this NFA accepts the concatenation of the two languages.

3. Iteration: We construct a NFA that recognizes $L_1^*$by taking $M_1$ and putting empty transitions from its final states to its start state. However, this construction has one problem, it does not accept the empty string unless the start state of $M_1$is also a final state, while $L_1^*$ includes the empty string. To correct this, we create a new start state, put empty transitions from all the final states to this state, and empty transitions from this state to the start state. It is easy to see that this NFA accepts $L_1^*$. Thus, given any regular expression, we can construct an automaton to accept the language described by it.

## Regular Languages are described by Regular Expressions

Theorem: If $L$ is a regular language, then it is described by a regular expression

Proof: Let $M = (Q,\Sigma,\Delta,q_0,F)$be the automaton that recognizes $L$. Given a subset $X \subseteq Q$and states $u,v \in Q$, we show how to construct a regular expression $R_{uv}^X$ representing the set of all strings $w$such that there is a path from $u$to $v$ in $M$ of the string $w$ and all the states in that path lie in $X$(with the possible exception of $u$and $v$). We construct this by induction on the size of $X$. $q$

Base Case : $X = \emptyset$

Let $a_1,a_2,\dots a_k$be the letters in $\Sigma \cup \{\epsilon \}$such that $v \in \Delta(u,a_i)$ for all $i$. Then, define

$R_{uv}^X :=\begin{cases}a_1\cup a_2 \cup \dots \cup a_k & k\geq 1 \\\emptyset & k=0\end{cases}$

Induction Step: For non-empty $X$, choose any state $q \in X$. We construct $R_{uv}^X$ as

$R_{uv}^X := R_{uv}^{X - \{q\}} \cup R_{uq}^{X-\{q\}}(R_{qq}^{X-\{q\}})^*R_{qv}^{X-\{q\}}$

By the induction hypothesis, each of $R_{uv}^{X-\{q\}}$, $R_{uq}^{X-\{q\}}$, $R_{qq}^{X-\{q\}}$ and $R_{qv}^{X-\{q\}}$ exist. To justify this expression, note that any path from $u$ to $v$ lying in $X$ will either never visit $q$, and hence the expression $R_{uv}^{X-\{q\}}$, or it visits $q$ for the first time, hence the expression $R_{uq}^{X-\{q\}}$, and then loops from $q$back to itself, hence the expression $R_{qq}^{X-\{q\}}$ and then reaches $v$ from $q$ and hence the expression $R_{qv}^{X-\{q\}}$

The regular expression for $L$ is

$R = \bigcup_{f \in F} R_{q_0f}^Q$

Thus, we have proved that Regular expressions characterise all the regular languages.

## MYHILL - NERODE THEOREM

Myhill - Nerode Relation: Let $L \subseteq \Sigma^*$ be any language. An equivalence realtion, $\equiv$ on $\Sigma^*$is said to be a Myhill - Nerode relation induced by $L$ if it satisfies the following properties:

1. Right congruence: $x \equiv y \implies \forall (w \in \Sigma^*) (xw \equiv yw)$

2. Refinement: $x \equiv y \implies (x \in L \iff y \in L)$

Theorem: Every regular language $L$ induces a Myhill-Nerode relation (MN relation) on $\Sigma^*$that has finitely many equivalence classes.​

Proof: Let $M = (Q,\Sigma,\delta,q_0,F)$ be the automaton recognizing $L$. For any state $q$ and word $w$ define $\hat{\delta}(q,w)$ inductively on the length of $w$ as

$\hat{\delta}(q,\epsilon) = q$

$\hat{\delta}(q,wa) = \delta(\hat{\delta}(q,w),a)$

This denotes the state of the automaton starting at state $q$ and reading the word $w$.

Now, define $\equiv_L$on $\Sigma^*$ as

$x \equiv_L y \iff \hat{\delta}(q_0,x) = \hat{\delta}(q_0,y)$

It is easy to see that this is an equivalence relation. Also, for any $w \in \Sigma^*$, if $x \equiv_L y$, then

$\hat{\delta}(q_0,xw) = \hat{\delta}(\hat{\delta}(q_0,x),w) = \hat{\delta}(\hat{\delta}(q_0,y),w) = \hat{\delta}(q_0,yw) \implies xw \equiv_L yw$

Hence, it is right congruent. Also,

$x \equiv_L y \implies \hat{\delta}(q_0,x) = \hat{\delta}(q_0,y) \implies (\hat{\delta}(q_0,x) \in F \iff \hat{\delta}(q_0,y) \in F) \implies (x \in L \iff y \in L)$

Hence, it is a MN relation. Also, it is clear from the definition that the number of equivalence classes is equal to the number of states of $M$ which is finite.

Theorem: Let $\equiv_L$ be a MN relation for any language $L \subseteq \Sigma^*$. If $\equiv_L$ is of finite index, i.e. it has finitely many equivalence classes, then $L$is regular.

Proof: We construct an automaton $M = (Q,\Sigma,\delta,q_0,F)$ for $L$ as follows:

$Q = \{ [x] \mid x \in \Sigma^*\}$ where $[x]$ is the equivalence class of $x$. Since there are finitely many equivalence classes, this set is finite.

$\delta([x],a) = [xa]$. This is well defined because of the right congruence of MN relations.

$q_0 = [\epsilon]$

$F = \{[x] \mid x\in L\}$

Claim: $\hat{\delta}([x],w) = [xw]$

We prove this by induction on length of $w$.

​Base case: $\hat{\delta}([x],\epsilon) = [x\epsilon] = [x]$ (By definition)​

Induction step: $\hat{\delta}([x],wa) = \delta(\hat{\delta}([x],w),a) = \delta([xw],a) = [xwa]$ (follows from definitions of $\delta$ and $\hat{\delta}$.

Hence, $w \in L(M) \iff \hat{\delta}([\epsilon],w) \in F \iff [w] \in F \iff w \in L$

Hence, $M$ is a DFA for $L$

Now, with these two results, we are ready to state the Myhill Nerode Theorem.

For any language $L \subseteq \Sigma^*$, define the canonical MN relation, $\approx_L$ on $\Sigma^*$ as

$x \approx_L y \iff (\forall w) (xw \in L \iff yw \in L)$

It is easy to see that this is a MN relation. Further more, this is the coarsest MN relation for $L$, i.e any other MN relation for $L$ refines this.

Lemma: Let $\equiv_L$ be a MN relation for $L$. Then, $\equiv_L$refines $\approx_L$.

Proof: Pick any $x,y$such that $x \equiv_L y$. Now, assume that $x \not\approx_L y$. This means that there exists some $w$ such that $xw \in L$ but $yw \notin L$. This implies that $xw \not\equiv_L yw$(since $\equiv_L$satisfies the refinement property). But this contradits the right congruence of $\equiv_L$. Hence, our assumption was wrong.

Thus, $x \equiv_L y \implies x \approx_L y$.

Thus, any MN relation refines the canonical MN relation.

Myhill - Nerode Theorem: A language $L$is regular iff ​ $\approx_L$ is of finite index.

Proof: If $\approx_L$ is of finite index, since $\approx_L$ is a MN relation, by our previous theorem, $L$is regular.

If $L$ is regular, it has some MN relation of finite index. By our previos result, this refines $\approx_L$. Hence, index of $\approx_L$is also finite. ​

## PUMPING LEMMA FOR REGULAR LANGUAGES

The pumping lemma gives a necessary condition for a language to be regular. The lemma is given below

Pumping Lemma: If $L$is a regular language, then there exists a natural number, $p \gt 0$ called the pumping length such that for any word $w \in L$of length greater than $p$, $w$can be written as $xyzw'$such that

1. $|xyz| = p$

2. $|y| \gt 0$

3. $xy^izw' \in L \forall i \geq 0$

This means that there is some segment of the word that can be pumped to get more words in the language.

Proof: Since $L$is regular, there is a deterministic finite automaton that recognizees it. Let the number of states in this automaton be $n$. The pumping length $p = n$. Now, consider any word $w$of length greater than $p$. Let $xyz$ be the first $p$ letters of the word. Consider the run of this word on the automaton. After the first $p$letters of the word are read, the run consists of $n+1$states. Since there are only $n$states in the machine, by the pigeon hole principle, a state must repeat in the run. Let the segement of the run that starts and ends at the same state be $y$. Then $w$is of the form $xyzw'$and since the automaton is at the same state before starting to read $y$and after finishing reading it, it is at the same state after reading $y^i$ for all $i \geq 0$. Hence, $xy^izw' \in L$ for all $i \geq 0$.​

Example: The language $L = \{ a^nb^n \mid n \geq 0\}$ is not a regular language.

Proof: Assume $L$ was a regular language. Then by the pumping lemma, there exists a pumping length $p$ for $L$. Consider the string $a^pb^p \in L$. If we write it as $xyzw'$such that $|xyz| \leq p$, then $xyz = a^p$ and $y = a^m$for some $0 \lt m \leq p$. Taking $i = 2$, we see that $xy^2zw' = a^{p+m}b^p \notin L$. This contradicts the pumping lemma. Hence, our assumption was wrong, and $L$ is not regular.

## BÜCHI AUTOMATA

Now that we are familiar with finite state automata, we study a particular type of automata that was developed to solve decidability problems in Second Order Logic. A Büchi automaton is an automaton that runs on strings of infinite length. Since it runs on infnite strings, we cannot use the standard definition of acceptance that we use for automaton over finite strings. We now formally define a Büchi automaton.

Infinite String: An infinite string over an alphabet $\Sigma$ is a function $\alpha : \mathbb{N} \rightarrow \Sigma$ where $\alpha[i]$ denotes the letter at the $i$th position.

A Büchi automaton is a Finite state automaton $A = (Q,\Sigma, \delta, q_0, F)$ that runs on infinite strings. To define acceptance condition for a Büchi automaton, we first look at the run of an infinite word on an automaton. Let $\rho$be the run of some word $\alpha$ on the automaton. Since it is an infinite word, and the automaton has finitely many states, some states must repeat infinitely often on the run $\rho$. We denote this set by $inf(\rho)$. Now, the automaton is said to accept $\alpha$ if the run of $\alpha$ on $A$ goes to some final state infinitely often i.e $inf(\rho) \cap F \neq \phi$.

We will denote a language of finite words over an alphabet $\Sigma$ by $L \subseteq \Sigma^*$ and a language of infinite words by $L \subseteq \Sigma^\omega$.

Example: Let $L$ be the language of all infinite strings over $\{a,b\}$ that have infinitely many $a$'s. The Büchi automaton recognizing this lagnuage is given below.

Büchi automaton that recognizes  $L$

Example: Let $L'$be the complement of the above language, that is language containing infinite strings that have only finitely many occurences of $a$. The Büchi automaton recognizing this language is given below. Note that it is a non-deterministic automaton.

Büchi automaton that recognizes  $L'$

## NON - DETERMINISTIC AND DETERMINISTIC BÜCHI AUTOMATA ARE NOT EQUIVALENT

Unlike automata over finite words, non-deterministic Büchi automata are more powerful than deterministic ones. To prove this, we will first characterise the languages recognized by deterministic Büchi automata.

Limit Language: Let $U \subseteq \Sigma^*$be any langugae of finite strings. The limit language of $U$is a language over infinite strings defined as

$lim(U) = \{\alpha \in \Sigma^\omega \mid \exists^\omega n \in \mathbb{N}, \alpha[0\dots n] \in U\}$

So, a word belongs to $lim(U)$ iff it has infinitely many prefixes in $U$.

Theorem: A language $L \subseteq \Sigma^\omega$is recognized by a deterministic Büchi automaton iff $L$is of the form $lim(U)$for some regular language $U \subseteq \Sigma^*$.

Proof: Let $U$ be a regular language of finite length words. Then, it is recognized by a deterministic automaton $A = (Q,\Sigma,\delta,q_0,F)$. If we interpret this automaton as a Büchi automaton, it is clear that it will accept $lim(U)$.

Conversely, if $L\subseteq \Sigma^\omega$is recognized by a deterministic Büchi automaton ​ $A = (Q,\Sigma,\delta,q_0,F)$, treating this as a DFA over finite words, it accepts some regular language $U$. It is easy to see that $L = lim(U)$.

Using this theorem, we will show that $L'$in our example above, cannot be recognized by a deterministic Büchi automaton. Assume otherwise. Then, by our theorem, $L' = lim(U)$ for some regular language $U \subseteq \Sigma^*$. Now, $b^\omega \in L'$. Thus, $b^{n_0} \in U$ for some $n_0$. Now, $b^{n_0}ab^\omega \in L'$. Thus, $b^{n_0}ab^{n_1} \in U$for some $n_1$. Continuing this process, we get an infinite set $\{b^{n_0},b^{n_0}ab^{n_1},b^{n_0}ab^{n_1}ab^{n_2}, \dots\}$ such that each of the strings in it lie in $U$. Then, the infinite string $b^{n_0}ab^{n_1}ab^{n_2}ab^{n_3}\dots$ lies in $L' (= lim(U))$. However, the string has infintely many $a$'s. Contradiction. Hence, $L$ cannot be recognized by a deterministic Büchi automaton.

## CLOSURE PROPERTIES OF BÜCHI RECOGNIZABLE LANGUAGES

A language recognized by a Büchi automata is called a Büchi recognizable language or a ω-regular language. We now study the closure of Büchi automata under the operations of union, intersection, projection and complementation.

1. Union: Let $L_1,L_2$be two Büchi recognizable languages. Then, $L_1\cup L_2$is also Büchi recognizable. Let $A_1,A_2$be the Büchi automata recognizing $L_1,L_2$respectively. We create a non deterministic Büchi automaton $A$ whose start states are the start states of $A_1$and $A_2$, and accept states are the union of accept states of $A_1$and $A_2$. This automaton runs the word on both $A_1$and $A_2$ and accepts if it is accepted by either of them. Hence, it accepts the union of the two languages.

2. Intersection: Let $A_1 = (Q_1,\Sigma, \Delta_1, S_1,F_1)$ and $A_2 = (Q_2,\Sigma, \Delta_2, S_2,F_2)$ be the (possibly non-deterministic) automata recognizing $L_1,L_2$ respectively. We construct an automaton that recognizes their intersection as follows, $A = (Q,\Sigma,\Delta,S,F)$, where

$Q = Q_1\times Q_2\times \{1,2\}$

$\Delta$is defined as:

$((q_1,q_2,1),a,(q_1',q_2',1))\in \Delta$ if $(q_1,a,q_1') \in \Delta_1, (q_2,a,q_2')\in \Delta, q_1 \notin F_1$

$((q_1,q_2,1),a,(q_1',q_2',2))\in \Delta$ if ​ $(q_1,a,q_1') \in \Delta_1, (q_2,a,q_2')\in \Delta, q_1 \in F_1$

$((q_1,q_2,2),a,(q_1',q_2',2))\in \Delta$ if ​ $(q_1,a,q_1') \in \Delta_1, (q_2,a,q_2')\in \Delta, q_2 \notin F_2$

$((q_1,q_2,2),a,(q_1',q_2',1))\in \Delta$ if ​ $(q_1,a,q_1') \in \Delta_1, (q_2,a,q_2')\in \Delta, q_2 \in F_2$

$S = \{(q_1,q_2,1) \mid q_1 \in S_1, q_2 \in S_2 \}$

$F = Q_1 \times F_2 \times \{2\}$

It is easy to verify that this automaton recognizes the intersection of the two languages.

3. Projection: Let $\Sigma_1, \Sigma_2$be two alphabets such that $|\Sigma_2| \leq |\Sigma_1|$. A projection map from $\Sigma_1$ to $\Sigma_2$is a surjective map​ $\pi : \Sigma_1 \rightarrow \Sigma_2$. We can extend this map to words as usual : if $\alpha \in \Sigma_1^\omega$​, $\pi(\alpha)$ is the word $\beta$ such that $\beta(i) = \pi(\alpha(i)) \forall i \in \mathbb{N}$. Let $L \subseteq \Sigma^\omega_1$be recognized by the Büchi automaton $A = (Q,\Sigma_1,\Delta,S,F)$, we construct an automaton $A' = (Q',\Sigma_2,\Delta',S',F')$that recognizes $\pi(L)$as follows:

$Q' = Q$

$(q,b,q') \in \Delta' if \exists a\in\Sigma_1 s.t. (q,a,q') \in \Delta; \pi(a) = b$

$S' = S$

$F' = F$

It is easy to verify that this automaton accepts the language $\pi(L)$.

4. Complementation: Showing that Büchi automata are closed under complementation is non-trivial, and we will devote an entire separate section for it.

## COMPLEMENTING BÜCHI AUTOMATA

Let $A = (Q,\Sigma,\Delta,S,F)$be a non-deterministic Büchi automaton that recognizes $L \subseteq \Sigma^\omega$. We define the run DAG of $A$on a word $\alpha \in \Sigma^\omega$to be the directed acyclic graph $G = (V,E)$where

1. $V = \bigcup_{l\geq0}(Q_l\times \{l\}) where Q_0 = S and Q_{l+1} = \bigcup_{q\in Q_l,(q,\alpha(l),q')\in\Delta}\{q'\}$

2. $E = \{ (\langle q,l\rangle,\langle q',l+1\rangle) \mid (q,\alpha(l),q')\in \Delta;l\geq0\}$

A path in a run DAG is accepting iff it visits $F$infinitely often. The automaton $A$ accepts $\alpha$if some path in the run DAG is accepting.

Now, we define a ranking for the run DAG as follows:

A ranking for $G$is a function $f : V \rightarrow \{0,1,2,\dots,2.|Q|\}$ such that

1. for all $\langle s,l \rangle \in V$, if $f(\langle s,l \rangle)$ is odd, then $s \notin F$

2. for all $( \langle s,l \rangle , \langle s',l' \rangle ) \in E, f(\langle s',l' \rangle) \leq f(\langle s,l \rangle)$

A ranking is called odd iff for all paths $\langle s_0,l_0 \rangle,\langle s_1,l_1 \rangle,\dots$in $G$, there is a $i \geq 0$ such that $f(\langle s_i,l_i \rangle)$ is odd and for all $j \gt i, f(\langle s_j,l_j \rangle) = f(\langle s_i,l_i \rangle)$

Lemma 1: If there exists an odd ranking for $G$, then $A$ does not accept $\alpha$

Proof: In an odd ranking, every path eventually gets trapped in an odd rank. If some vertex $\langle s,l \rangle$is odd, then $s \notin F$. Hence, all paths visit $F$ only finitely many times.

Let $G'$ be a subgraph of $G$. We call a vertex $\langle s,l \rangle$

1. Safe in $G'$if for all vertices $\langle s',l' \rangle$reachable from $\langle s,l \rangle$, $s' \notin F$

2. Endangered in $G'$ if only finitely many vertices are reachable from it.

We define a sequence of DAG's $G_0 \supseteq G_1 \supseteq G_2 \supseteq \dots$inductively as follows

1. $G_0 = G$

2. $G_{2i + 1} = G_{2i} \setminus \{\langle s,l \rangle \mid \langle s,l \rangle is endangered in G_{2i}\}$

3. $G_{2i + 2} = G_{2i + 1} \setminus \{\langle s,l \rangle \mid \langle s,l \rangle is safe in G_{2i} \}$

Lemma 2: If $A$ does not accept $\alpha$, then the following holds: for every $i \geq 0$, there exists an $l_i$ such that for all $j \geq l_i$, at most $|Q| - i$ vertices of the form $\langle \_,j \rangle$ are in $G_{2i}$

Proof: We prove by induction on $i$.

Base case : $i = 0$ is trivial.

Inductive case: Assume truth for $0,1,2,\dots ,i$.

Case $G_{2i}$is finite: then $G_{2(i+1)}$ is empty.

Case $G_{2i}$ is infinite:

- There must exist a safe vertex $\langle s,l \rangle$ in $G_{2i+1}$

- ​We choose $l_{i+1} = l$

- We prove that for all $j \geq l$, there are atmost $|Q| - (i+1)$vertices of the form $\langle \_,j \rangle$ in $G_{2i + 2}$:

1. $\langle s,l \rangle \in G_{2i+1}$, thus, it is not endangered in $G_{2i}$. Hence, there are infintely many verties reachable from $\langle s,l \rangle$ in $G_{2i}$.

2. By König's lemma, there exists an infinte path $p = \langle s,l \rangle, \langle s_1,l+1 \rangle,\dots$ in $G_{2i}$ and no vertex in this path is endangered in $G_{2i}$. Thus, $p$is in $G_{2i + 1}$

3. All vertices in $p$ are safe in $G_{2i+1}$. Hence, none of the vertices of $p$ are in $G_{2i+2}$.

Hence Proved.

Lemma 3: If $A$ does not accept $\alpha$, then there exists an odd ranking for $G$.

Proof: We define $f(\langle s,l \rangle) = 2i$if $(\langle s,l \rangle)$is endangered in $G_{2i}$ and ​ $f(\langle s,l \rangle) = 2i+1$if $(\langle s,l \rangle)$is safe in $G_{2i}$.

$f$ is a ranking

By Lemma 2, $G_j$is empty for $j \gt 2.|Q|$. Hence, $f : V \rightarrow \{0,1,2,\dots,2.|Q|\}$

If $\langle s',l' \rangle$is a succesor of $\langle s,l \rangle$​, then $f(\langle s',l' \rangle) \leq f(\langle s,l \rangle)$:

Let $j = f(\langle s,l \rangle)$. If $j$is even, $\langle s,l \rangle$​is endangerd in $G_j$ and hence, either $\langle s',l' \rangle$is not in $G_j$and hence $f(\langle s',l' \rangle) \lt j$; or $\langle s',l' \rangle$ is in $G_j$and safe; and hence, $f(\langle s',l' \rangle) = j$

$f$is an odd ranking: It is clear that for every path, there is an $i \geq 0$ such that for all $j\geq i$ $f(\langle s_j,l_j \rangle) = f(\langle s_i,l_i \rangle)$. Now, suppose $k = f(\langle s_i,l_i \rangle)$is even. Then, ​ $\langle s_i,l_i \rangle$is endangered in $G_k$. But, since $f(\langle s_j,l_j \rangle) = f(\langle s_i,l_i \rangle)$ for all $j\geq i$, all $\langle s_j,l_j \rangle$ are in $G_k$. This contradicts that ​ $\langle s_i,l_i \rangle$is endangered in $G_k$. Hence, proved.

Theorem: For every Büchi automaton $A$, there exists a Büchi automaton $A'$ such that $L(A')$is the complement of $L(A)$

Proof: We first define some helpful structures:

1. A level ranking is a function $g : Q \rightarrow \{0,1,\dots,2.|Q|\} \cup \{\bot\}$ such that if $g(q)$is odd, then $q \notin F$.

2. Let $R$ be the set of all level rankings

3. A level ranking $g'$ covers a level ranking $g$ if, for all $q,q' \in Q$, if $g(q) \geq 0$and $(q,a,q') \in \Delta$, then $0 \leq g'(q') \leq g(q)$​.

We now construct $A' = (Q',\Sigma,\Delta',S',F')$ as follows:

$Q' = R \times 2^Q$

$S' = \{ \langle g_0,\emptyset \rangle, where g_0(q) = 2.|Q| if q\in S and g_0(q) = \bot if q\notin S\}$

$\Delta' = \{(\langle g,\emptyset \rangle,a,\langle g',P' \rangle \mid g'$covers $g,$and $P' = \{q' \in Q \mid g'(q')$is even $\}\}$

$\cup \{ (\langle g,P \rangle,a,\langle g',P' \rangle) \mid P \neq \emptyset , g'$covers $g$, and

$P' = \{q'\in Q \mid (q,a,q') \in \Delta, q\in P, g'(q')$is even $\}\}$

$F' = R \times \{\emptyset\}$

It is not very difficult to see that this automaton accepts the complement language

## MONADIC SECOND - ORDER THEORY OF ONE SUCCESSOR

The logic that Büchi considered was the monadic second order logic of one succesor, abbreviated as S1S. This language is defined formally as follows:

Terms: A term in S1S is built up from the constant 0 and individual variables $x,y,\dots$ and by the application of the successor function, $succ$. Examples : $0,succ\left(x\right),succ\left(succ\left(y$