Introduction to Computability Theory
Finite Automata and Regular Languages
Prof. Amos Israeli
1
Introduction
Computer Science stems from two starting points:
Mathematics: What can be computed?
And what cannot be computed?
Electrical Engineering: How can we build computers?
Not in this course.
2
Introduction
Computability Theory deals with the profound mathematical basis for Computer Science, yet it has some interesting practical ramifications � that I will try to point out sometimes.
The question we will try to answer in this course is:
“What can be computed? What Cannot be computed and where is the line between the two?”
3
Computational Models
A Computational Model is a mathematical object (Defined on paper) that enables us to reason about computation and to study the properties and limitations of computing.
We will deal with Three principal computational models in increasing order of Computational Power.
4
Computational Models
We will deal with three principal models of computations:
5
Alan Turing - A Short Detour
Dr. Alan Turing is one of the founders of Computer Science (he was an English Mathematician). Important facts:
6
Finite Automata - A Short Example
Control of a Simple Washing Machine
25
25
25
25
Finite Automata - A Short Example
25
25,50
25,50
25
50
50
Finite Automata - A Short Example
25
25,50,100
25
50
50,100
100
25,50,100
Finite Automaton - An Example
11
0
1
States:
0,1
0,1
Initial State:
Final State:
Finite Automaton – An Example
12
,
,
0
1
0,1
0,1
Accepted words:
Transition Function:
Alphabet: .
Note: Each state has all transitions .
Finite Automaton – Formal Definition
A finite automaton is a 5-tupple �where:
13
,
,
Observations
14
,
,
Examples
�
15
How to do it
The automaton
Correctness Argument:
The FA’s states encode the last input bit and is the only accepting state. The transition function preserves the states encoding.
1
0
1
0
1
0
Examples
2’. accepts all words ending with 0 and the empty word .
This is the Complement Automaton of .
18
Examples
19
Examples (cont)
20
Languages
21
Languages
22
,
Some Questions
Q1: How do you prove that a language is regular?
A1: By presenting an FA, , satisfying .
Q2: Why is it important?
A2: Recognition of a regular language requires a controller with bounded Memory.
Q3: How do you prove that a language is not regular?
A3: Hard! to be answered on Week3 of the course.
23
Wrap up
In this talk we:
24
Example of an NFA
25
0,1
0,1
1
1
,0
1. A state nay have 0 or more transitions labeled with � the same symbol.
2. transitions are possible.
NFA – Nondeterministic Finite Automaton
Computation of an NFA
Q:Which words are accepted and which are not?
A: If word w induces (at least) a single accepting path, the automaton “chooses” this accepting path and w is accepted.
26
Possible Computations
27
DFA
.
.
.
. . . .
NFA
At each step of the computation: DFA - A single state is occupied.
NFA - Several states may be � occupied.
Computation of an NFA - Example
28
On the input word w=01011 there exist an accepting path and w is accepted.
Can we characterize (find) the language recognized by this automaton?
Words containing either 101 or 11 as substrings.
0,1
0,1
1
1
,0
Computation tree of 01011
29
0,1
1
1
,0
0,1
0
1
1
0
0
1
1
1
1
1
1
Accepting branch
Why do we Care About NFAs?
(Note: This statement must be proved.)
30
Example - A Complicated DFA
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
Example – An Equivalent NFA
Can you guess the language?
1
0,1
0,1
0,1
Bit Strings that have 1 in position third from the end
Example - A Complicated DFA
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
Can you verify it now?
DFA – A Formal Definition(Rerun)
A finite automaton is a 5-tupple �where:
34
NFA – A Formal Definition
A finite automaton is a 5-tupple �where:
35
Differences between NFA-s and DFA-s
There are two differences:
1. The range of the transition function is now � . (The set of subsets of the state set )
2. The transition function allows transitions.
36
Computations of NFA-s
In general a computation of an NFA, N, on input w, induces a computation tree.
Each path of the computation tree represents a possible computation of N.
The NFA N accepts w, if its computation tree includes at least one path ending with an accepting state.
37
Computations of NFA-s
There are two ways to look at computations of an NFA:
38
Equivalence Between DFAs and NFAs
Now we prove that the class of NFAs is Equivalent to the class of DFA:
Theorem: For every NFA , there exists a DFA� , such that .
Proof Idea: The proof is Constructive: We assume that we know , and construct a simulating DFA, .
39
Construction Demonstration
40
We start with an NFA with no transitions.
The equivalent DFA is denoted by:
0,1
0,1
1
0
Construction Demonstration
The state set of the equivalent DFA, D, should reflect the fact that at each step of the computation, N may occupy several sates, Thus we define the state set of D as �the power-set of the state set of N, namely:
Construction Demonstration
Recall that the transition function of any NFA is defined by .
Do not be confused by the use of as the state set of D . D is a DFA, not the original NFA.
Construction Demonstration
The alphabet of D, , is identical to the alphabet of N.
The starting state of D corresponds to the starting state of N, namely .
The most complex part of the construction is the transition function:
In the sequel it is demonstrated stage by stage:
Construction Demonstration
�
Since the only state reachable from by 0 is ,
we get .
0,1
0,1
1
0
0
Construction Demonstration
Since both and are reachable from by 1,
we get .
0,1
0,1
1
0
0
1
Construction Demonstration
Similarly we get .
0,1
0,1
1
0
0
1
1
Construction Demonstration
and .
0,1
0,1
1
0
0
1
0
1
Construction Demonstration
Since and ,�we get .
0,1
0,1
1
0
0
0
1
0
1
1
Construction Demonstration
Finally we get the following DFA:
0,1
0,1
1
0
1
0
0
1
0
0
1
1
Construction Demonstration
And its disconnected section:
1
0
0
1
0
0
1
0
0
1
0
0
1
1
1
Construction Demonstration
Since 1,0 is accepted we get that is an accepting state.
0,1
0,1
1
0
1
0
0
1
0
0
1
1
Construction Demonstration
Since 1,0,1 is accepted we get that is also an accepting state.
0,1
0,1
1
0
1
0
0
1
0
0
1
1
Wrap Up
In this lecture we:
53
Equivalence Between DFAs and NFAs
Every DFA is (A special case of) an NFA, hence� , but .
Nevertheless, these classes are Equivalent.
This means that for any NFA N there exists a DFA D satisfying: .
54
Equivalence Between DFAs and NFAs
Thus, to prove equivalence of the classes we prove:
Theorem: For every NFA N there exists a DFA D satisfying :
Proof Idea: The proof is Constructive: We assume that we know , and construct a simulating DFA, D .
55
Proof
Let recognizing some language A. The state set of the simulating DFA D, should reflect the fact that at each step of the computation, N may occupy several sates.
Thus we define the state set of D as �the power-set of the state set of N.
56
Proof (cont.)
Let recognizing some language A. First we assume that N has no � - transitions.
Define where .
57
Proof (cont.)
Our next task is to define D’s transition function, : �For any and define
If R is a state of M, then it is a set of states of N. When M in state R processes an input symbol a, M goes to the set of states to which N will go in any of the branches of its computation.
58
Proof (cont.)
An alternative way to write the definition of M’s transition function, is: �For any and define
And the explanation is just the same.
Note: if than
Which is OK since .
59
Proof (cont.)
The initial state of M is: � .
Finally, the final state of M is: �
Since D accepts if N reaches at least one accepting state.
The reader can verify for her/him self that D indeed simulates N .
60
Proof (cont.)
It remains to consider - transitions.
For any state of D define to be the collection of states of R unified with the states reachable from R by - transitions. The old definition of is:
And the new definition is:
61
Proof (end)
In addition, we have to change the definition of � , the initial state of . The previous definition, , is replaced with� .
Once again the reader can verify that the new definition of D satisfies all requirements.
62
Corollary
A language L is regular if and only if there exists an NFA recognizing L .
63
The Regular Operations
Let and be 2 regular languages above the same alphabet, . We define the 3 Regular Operations:
64
Elaboration
65
The Regular Operations - Examples
66
Motivation for Nondeterminism
We want to use the regular operations for a systematic construction of all regular expressions.
Given a two DFA-s, their product DFA can recognizes their union, but we do not know how to construct a DFA recognizing either concatenation or star.
This can be proved by using NFA-s.
67
Theorem
The class of Regular languages is closed under the all three regular operations.
.
68
Proof for union Using NFA-s
If and are regular, each has its own recognizing automaton and , respectively.
In order to prove that the language is regular we have to construct an FA that accepts exactly the words in .
69
A Pictorial proof
70
F
Proof for union Using NFA-s
Let recognizing A1 , and � recognizing A2 .
Construct to recognize ,
Where , ,
71
Theorem
The class of Regular languages is closed under the concatenation operation. � .
72
Proof idea
Given an input word to be checked whether it belongs to , we may want to run until it reaches an accepting state and then to move to .
73
Proof idea
The problem: Whenever an accepting state is reached, we cannot be sure whether the word of is finished yet.
The idea: Use non-determinism to choose the right point in which the word of is finished and the word of starts.
74
A Pictorial proof
75
F
Proof using NFAs
Let recognizing A1 , and � recognizing A2 .
Construct to recognize ,
Where , ,
76
Theorem
The class of Regular languages is closed under the star operation. � .
77
A Pictorial proof
78
F
Proof using NFAs
Let recognizing A1 .
Construct to recognize
Where , , and
79
Wrap Up
In this lecture we:
80
Introduction
Regular languages are defined and described by use of finite automata.
In this lecture, we introduce Regular Expressions as an equivalent way, yet more elegant, to describe regular languages.
81
Motivation
If one wants to describe a regular language, La, she can use the a DFA, D or an NFA N, such that that .
This is not always very convenient.
Consider for example the regular expression� describing the language of binary strings containing a single 1.
82
Basic Regular Expressions
A Regular Expression (RE in short) is a string of symbols that describes a regular Language.
83
Inductive Construction
Let and be two regular expressions representing languages and , resp.
84
Inductive Construction - Remarks
85
Inductive Construction - Remarks
Stage 1: Prove T correct for all base cases.
Stage 2: Assume T is correct for and . � Prove correctness for , , � and .
86
Some Useful Notation
Let be a regular expression:
87
Precedence Rules
88
Examples
89
Examples
90
Equivalence With Finite Automata
Regular expressions and finite automata are equivalent in their descriptive power. This fact is expressed in the following Theorem:
Theorem�A set is regular if and only if it can be described by a regular expression.
The proof is by two Lemmata (Lemmas):
91
,
Lemma ->
If a language L can be described by regular expression then L is regular.
92
,
,
Proofs Using Inductive Definition
The proof follows the inductive definition of RE-s as follows:
Stage 1: Prove correctness for all base cases.
Stage 2: Assume correctness for and , and show its correctness for , and� .
93
Induction Basis
94
The Induction Step
Now, we assume that and represent two regular sets and claim that , and represent the corresponding regular sets.
The proof for this claim is straight forward using the constructions given in the proof for the closure of the three regular operations.
95
Examples
Show that the following regular expressions represent regular languages:
To be demonstrated on the Blackboard.
96
Lemma <-
If a language L is regular then L can be described by some regular expression.
97
Proof Stages
The proof follows the following stages:
98
,
Properties of a Generalized NFA
99
,
Example of a Generalized NFA
100
A Computation of a GNFA
A computation of a GNFA is similar to a computation of an NFA. except:�In each step, a GNFA consumes a block of symbols that matches the RE on the transition used by the NFA.
101
Example of a GNFA Computation
Consider abba or bb or abbbaaaaabbbbb
102
Converting a DFA (or NFA) to a GNFA
Conversion is done by a very simple process:
103
Converting a DFA to a GNFA (Cont)
104
Stage 1: Convert D to a GNFA
1.0 Start with D
105
Stage 1: Convert D to a GNFA
1.1 Add 2 new states
106
Stage 1: Convert D to a GNFA
1.2 Make the initial state and the final�state.
107
Stage 1: Convert D to a GNFA
1.3 Replace multi label transitions by their union.
108
Stage 1: Convert D to a GNFA
1.4 Add all missing transitions and label them .
109
Ripping a state from a GNFA
The final element needed for the proof is a procedure in which for any GFN G, any state of G, not including and , can be ripped off G, while preserving .�This is demonstrated in the next slide by considering a general state, denoted by , and an arbitrary pair of states, and , as demonstrated in the next slide:
110
Removing a state from a GNFA
111
Before Ripping
After Ripping
Note: This should be done for every pair of outgoing and incoming outgoing .
Ellaboration
Consider the RE ,�representing all strings �that enable transition �from via to .
What we want to do is to augment the Regular expression of transition , namely , so These strings can pass through . This is done by setting it to .
112
Ellaboration
Note: In order to achieve �an equivalent GNFA in �which is disconnected,�this procedure should be�carried out separately, for every�pair of transitions of the form and � . Then can be removed, as demonstrated on the next slide:
113
Elaboration
Assume the following situation:�In order to rip , all pairs�of incoming and outgoing�transitions should be considered �in the way showed on the �previous slide namely consider� � one after the other. After that can be ripped while preserving .
114
In Particular
Replace with .
�
115
A (half?) Formal Proof of Lemma<-
The first step is to formally define a GNFA.
Each transition should be labeled with an RE.
Define the transition function as follows: �
�where denotes all regular expressions over .
Note: The def. of is different then for NFA.
116
Changes in Definition
Note: The definition of as:
�is different than the original definitions (For DFA and NFA).
In this definition we rely on the fact that every 2 states (except and ) are connected in both directions.
117
GNFA – A Formal Definition
A Generalized Finite Automaton is a 5-tupple � where:
118
GNFA – Defining a Computation
A GNFA accepts a string if �and there exists a sequence of states � , satisfying:
For each , , , where� , or in other words, is the expression on the arrow from to .
119
Procedure CONVERT
Procedure CONVERT takes as input a GNFA G with k states.
If then these 2 states must be and � , and the algorithm returns
.
If , the algorithm converts G to an equivalent G’ with states by use of the ripping procedure described before.
120
Procedure CONVERT
Convert
�for �return ;
121
Recap
In this lecture we:
122
Introduction and Motivation
In this lecture we ask: Are all languages regular?
The answer is negative.
The simplest example is the language�
Try to think about this language.
123
Introduction and Motivation
If we try to find a DFA that recognizes the language , , it seems that we need an infinite number of states, to “remember” how many a-s we saw so far.
Note: This is not a proof!
Perhaps a DFA recognizing B exists, but we are not clever enough to find it?
124
Introduction and Motivation
The Pumping Lemma is the formal tool we use to prove that the language B (as well as many other languages) is not regular.
125
What is Pumping?
Consider the following NFA, denoted by N:
It accepts all words of the form .
126
What is Pumping?
Consider now the word .
Pumping means that the word can be divided into two parts: 1 and 10, such that for any , the word .
We say that the word 110 can be pumped.
For this is called down pumping.
For this is called up pumping.
127
What is Pumping?
A more general description would be:�A word , can be pumped if and for each , it holds that .
Note: the formal definition is a little more complex than this one.�
128
The Pumping Lemma
Let A be a regular language. There exists a number p such that for every , if � then w may be divided into three parts , satisfying:
Note: Without req. 2 the Theorem is trivial.
129
Demonstration Continuation
In terms of the previous demonstration we have:
.� .� .
130
Proof of the Pumping Lemma
Let D be a DFA recognizing A and let p be the number of states of D. If A has no words whose length is at least p, the theorem holds vacuously. Let be an arbitrary word such that . Denote the symbols of w by where .
131
Proof of the Pumping Lemma
Assume that is the sequence of states that D goes through while computing with input w. For each , , � . Since , .
Since the sequence contains �states and since the number of states of D is p, that there exist two indices , such that .
132
Proof of the Pumping Lemma
Denote , and � .
Note: Under this definition and .
By this definition, the computation of D on � starting from , ends at .
By this definition, the computation of D on � , starting from , ends at which is an accepting state.
133
Proof of the Pumping Lemma
The computation of D on �starting from , ends at . Since , this computation starts and ends at the same state.
Since it is a circular computation, it can repeat itself k times for any .
In other words: for each , .
Q.E.D.
134
Example: .
Lemma: The language is not regular.
Proof: Assume towards a contradiction that L is regular and let p be the pumping length of L.
Let . By the Pumping Lemma there exists a division of w, , such that � , and w can be pumped.
This means that , where .
Since we conclude
135
Example: (Cont.)
This however implies that in , the number of a-s is smaller then the number of b-s.
It also means that for every , the number of a-s in is larger then the number of �b-s. Both cases constitute a contradiction.
Note: Each one of these cases is separately sufficient for the proof.
136
Discussion
This is what we got so far:
�
137
RL-s Ex:
Lecture Recap
138