An introduction to finite automata theory
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
The following abbreviations will be used in this report
|DFA||Deterministic Finite Automata|
|NFA||Non-Deterministic Finite Automata|
|S1S||Monadic second order logic of one successor|
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.
FINITE AUTOMATA: A FORMAL DEFINITION
A Finite Automata is defined as a quintuple where :
1. is a finite set called the set of states
2. is a finite set called the Alphabet
3. is a function called the Transition Function
4. is a state called the Initial State
5. is called the set of Accept States
The input to a Finite Automaton are words from the alphabet . A Finite Automaton always begins in the initial state. As it reads a word (call it ), 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 . 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 be a finite automaton, and let be a word where each belongs to the alphabet . Then, accepts if there exist a sequence of states in (such a sequence of states is called an accepting run of the word on the automaton ) such that:
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, , 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.
Example 2: Consider the language, , over the alphabet that contains all strings that contain the substring . The idea behind this construction is to check for the substring while reading the string, and then accepting if we find it. The automaton that accepts this language is shown below.
A language, , is said to be a Regular Language if it is recognized by some finite automaton.
Observe that, given a word , 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 ). 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 where
1. is the set of states
2. is the Alphabet
3. is a relation called the Transition Relation
4. is a state called the Initial State
5. is called the set of Accept States
Observe that a NFA has a transition relation instead of a function i.e given a state and input letter , the machine can go to state iff . This relation introduces the non-determinism in the machine. Similar to a DFA, we define an accepting run of a word on a NFA as a sequence of states where (the run can be much larger than the length of the input because of empty transitions) such that
We say that a NFA accepts a word if there exists atleast one accepting run of 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 of all strings over that have a at the third position from the end of the string. We can construct a NFA to accept this language by guessing that each 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
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:
Proof: Let be a NFA. We construct a DFA, , that is equivalent to as follows :
1. , the set of all subsets of
2. To define the transition function, we first define as the set of all states reachable from on the letter in the NFA i.e . Now we define the transition function for as
3. The start state is the state corresponding to the singleton set
4. The set of final states consists of all the subsets of that contain atleast one final state from i.e
The machine keeps track of all the states the NFA is in after reading the input. Hence, if after reading the input is in a state from , then there was some run in that ended in a final state, and hence, the input is accepted by . It is easy to see that these two automata are equivalent.
We now try to give a characterisation of the regular languages. For this purpose, we define three operations on languages. Let and be two languages. We define :
1. Union :
2. Concatenation :
3. Iteration : (Note that this also contains the empty string)
Now, we define regular expressions inductively as follows:
1. The expression is a regular expression ( is a letter of some alphabet )
2. which denotes the empty string, is a regular expression
3. which denotes the empty language, is a regular expression
4. If and are regular expressions, then
4.1 is a regular expression
4.2 is a regular expression
4.2 is a regular expression
1. is a regular expression that describes the language of all strings over the alphabet
2. is a regular expression that describes all strings starting with an and ending with a
Now, we will prove that regular languages can be characterised using regular expressions. This includes two parts.
Regular Expressions describe Regular Languages
Theorem : If 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.
2. Empty String : The expression describes the language consisting of only the empty string i.e . This is also a regular language as it can be recognized by the following one state automaton
3. Null language: The expression 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 and be regular expressions and let their corresponding regular languages be and respectively (this is true from the induction hypothesis). Let the automata recognizing and be and 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 and . We keep and as they are, and make the set of final states the union of their final states. This NFA runs the word on both and 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 by taking and putting empty transitions from the final states of to the start states of . The start state of this new NFA is the start state of and the final states are the final states of . It is easy to see that this NFA accepts the concatenation of the two languages.
3. Iteration: We construct a NFA that recognizes by taking 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 is also a final state, while 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 . 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 is a regular language, then it is described by a regular expression
Proof: Let be the automaton that recognizes . Given a subset and states , we show how to construct a regular expression representing the set of all strings such that there is a path from to in of the string and all the states in that path lie in (with the possible exception of and ). We construct this by induction on the size of .
Base Case :
Let be the letters in such that for all . Then, define
Induction Step: For non-empty , choose any state . We construct as
By the induction hypothesis, each of , , and exist. To justify this expression, note that any path from to lying in will either never visit , and hence the expression , or it visits for the first time, hence the expression , and then loops from back to itself, hence the expression and then reaches from and hence the expression
The regular expression for is
Thus, we have proved that Regular expressions characterise all the regular languages.
MYHILL - NERODE THEOREM
Myhill - Nerode Relation: Let be any language. An equivalence realtion, on is said to be a Myhill - Nerode relation induced by if it satisfies the following properties:
1. Right congruence:
Theorem: Every regular language induces a Myhill-Nerode relation (MN relation) on that has finitely many equivalence classes.
Proof: Let be the automaton recognizing . For any state and word define inductively on the length of as
This denotes the state of the automaton starting at state and reading the word .
Now, define on as
It is easy to see that this is an equivalence relation. Also, for any , if , then
Hence, it is right congruent. Also,
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 which is finite.
Theorem: Let be a MN relation for any language . If is of finite index, i.e. it has finitely many equivalence classes, then is regular.
Proof: We construct an automaton for as follows:
where is the equivalence class of . Since there are finitely many equivalence classes, this set is finite.
. This is well defined because of the right congruence of MN relations.
We prove this by induction on length of .
Base case: (By definition)
Induction step: (follows from definitions of and .
Hence, is a DFA for
Now, with these two results, we are ready to state the Myhill Nerode Theorem.
For any language , define the canonical MN relation, on as
It is easy to see that this is a MN relation. Further more, this is the coarsest MN relation for , i.e any other MN relation for refines this.
Lemma: Let be a MN relation for . Then, refines .
Proof: Pick any such that . Now, assume that . This means that there exists some such that but . This implies that (since satisfies the refinement property). But this contradits the right congruence of . Hence, our assumption was wrong.
Thus, any MN relation refines the canonical MN relation.
Myhill - Nerode Theorem: A language is regular iff is of finite index.
Proof: If is of finite index, since is a MN relation, by our previous theorem, is regular.
If is regular, it has some MN relation of finite index. By our previos result, this refines . Hence, index of 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 is a regular language, then there exists a natural number, called the pumping length such that for any word of length greater than , can be written as such that
This means that there is some segment of the word that can be pumped to get more words in the language.
Proof: Since is regular, there is a deterministic finite automaton that recognizees it. Let the number of states in this automaton be . The pumping length . Now, consider any word of length greater than . Let be the first letters of the word. Consider the run of this word on the automaton. After the first letters of the word are read, the run consists of states. Since there are only 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 . Then is of the form and since the automaton is at the same state before starting to read and after finishing reading it, it is at the same state after reading for all . Hence, for all .
Example: The language is not a regular language.
Proof: Assume was a regular language. Then by the pumping lemma, there exists a pumping length for . Consider the string . If we write it as such that , then and for some . Taking , we see that . This contradicts the pumping lemma. Hence, our assumption was wrong, and is not regular.
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 is a function where denotes the letter at the th position.
A Büchi automaton is a Finite state automaton 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 be the run of some word 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 . We denote this set by . Now, the automaton is said to accept if the run of on goes to some final state infinitely often i.e .
We will denote a language of finite words over an alphabet by and a language of infinite words by .
Example: Let be the language of all infinite strings over that have infinitely many 's. The Büchi automaton recognizing this lagnuage is given below.
Example: Let be the complement of the above language, that is language containing infinite strings that have only finitely many occurences of . The Büchi automaton recognizing this language is given below. Note that it is a non-deterministic automaton.
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 be any langugae of finite strings. The limit language of is a language over infinite strings defined as
So, a word belongs to iff it has infinitely many prefixes in .
Theorem: A language is recognized by a deterministic Büchi automaton iff is of the form for some regular language .
Proof: Let be a regular language of finite length words. Then, it is recognized by a deterministic automaton . If we interpret this automaton as a Büchi automaton, it is clear that it will accept .
Conversely, if is recognized by a deterministic Büchi automaton , treating this as a DFA over finite words, it accepts some regular language . It is easy to see that .
Using this theorem, we will show that in our example above, cannot be recognized by a deterministic Büchi automaton. Assume otherwise. Then, by our theorem, for some regular language . Now, . Thus, for some . Now, . Thus, for some . Continuing this process, we get an infinite set such that each of the strings in it lie in . Then, the infinite string lies in . However, the string has infintely many 's. Contradiction. Hence, 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 be two Büchi recognizable languages. Then, is also Büchi recognizable. Let be the Büchi automata recognizing respectively. We create a non deterministic Büchi automaton whose start states are the start states of and , and accept states are the union of accept states of and . This automaton runs the word on both and and accepts if it is accepted by either of them. Hence, it accepts the union of the two languages.
2. Intersection: Let and be the (possibly non-deterministic) automata recognizing respectively. We construct an automaton that recognizes their intersection as follows, , where
is defined as:
It is easy to verify that this automaton recognizes the intersection of the two languages.
3. Projection: Let be two alphabets such that . A projection map from to is a surjective map . We can extend this map to words as usual : if , is the word such that . Let be recognized by the Büchi automaton , we construct an automaton that recognizes as follows:
It is easy to verify that this automaton accepts the language .
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 be a non-deterministic Büchi automaton that recognizes . We define the run DAG of on a word to be the directed acyclic graph where
A path in a run DAG is accepting iff it visits infinitely often. The automaton accepts if some path in the run DAG is accepting.
Now, we define a ranking for the run DAG as follows:
A ranking for is a function such that
1. for all , if is odd, then
2. for all
A ranking is called odd iff for all paths in , there is a such that is odd and for all
Lemma 1: If there exists an odd ranking for , then does not accept
Proof: In an odd ranking, every path eventually gets trapped in an odd rank. If some vertex is odd, then . Hence, all paths visit only finitely many times.
Let be a subgraph of . We call a vertex
1. Safe in if for all vertices reachable from ,
2. Endangered in if only finitely many vertices are reachable from it.
We define a sequence of DAG's inductively as follows
Lemma 2: If does not accept , then the following holds: for every , there exists an such that for all , at most vertices of the form are in
Proof: We prove by induction on .
Base case : is trivial.
Inductive case: Assume truth for .
Case is finite: then is empty.
Case is infinite:
- There must exist a safe vertex in
- We choose
- We prove that for all , there are atmost vertices of the form in :
1. , thus, it is not endangered in . Hence, there are infintely many verties reachable from in .
2. By König's lemma, there exists an infinte path in and no vertex in this path is endangered in . Thus, is in
3. All vertices in are safe in . Hence, none of the vertices of are in .
Lemma 3: If does not accept , then there exists an odd ranking for .
Proof: We define if is endangered in and if is safe in .
is a ranking
By Lemma 2, is empty for . Hence,
If is a succesor of , then :
Let . If is even, is endangerd in and hence, either is not in and hence ; or is in and safe; and hence,
is an odd ranking: It is clear that for every path, there is an such that for all . Now, suppose is even. Then, is endangered in . But, since for all , all are in . This contradicts that is endangered in . Hence, proved.
Theorem: For every Büchi automaton , there exists a Büchi automaton such that is the complement of
Proof: We first define some helpful structures:
1. A level ranking is a function such that if is odd, then .
2. Let be the set of all level rankings
3. A level ranking covers a level ranking if, for all , if and , then .
We now construct as follows:
covers and is even
covers , and
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 and by the application of the successor function, . Examples :