HCT- Department of IT
Formal Language and Automata Theory
CHAPTER 2 FINITE STATE AUTOMATA & THEIR LANGUAGES
Objectives Objectives At the end of this chapter, the students will be able to understand:
[Link] deterministic finite automata (DFA)? 2. Extended transition function 3. Define Languages of the DFA 4. Evaluate minimization of the DFA.
INTRODUCTION
Now time has come to define formally concept of finite automaton which is called
Chapter 2 Finite state Automata & Their Languages
Page - -
13
HCT- Department of IT
Formal Language and Automata Theory
2.1. DETERMINISTIC FINITE STATE AUTOMATA & THEIR LANGUAGES
2.1.1. Definition of Deterministic Finite Automaton
2.1.2. Simpler Notations for DFA's
Chapter 2 Finite state Automata & Their Languages
Page - -
14
HCT- Department of IT
Formal Language and Automata Theory
[Link]. Transition Diagram
Example 2.1
Problem: Let us formally specify a DFA that accepts all and only the
Figure 2.1 Shows the transition diagram for the DFA that is designed for this problem Explained in above lines. We see in the diagram (Figure 2.1) the three nodes that cor-
Figure 2.1. The transition diagram for the DFA accepting all strings with a substring 01
Chapter 2 Finite state Automata & Their Languages
Page - -
15
HCT- Department of IT
Formal Language and Automata Theory
[Link]. Transition Table
Transition table has * and
which indicate accepting and start state in the DFA.
Figure 2.2. Transition Table for the DFA of example 2.1
2.1.3. How a DFA processes Strings
If we look at the example 2.1, formal definition of the automaton where end of the string is 01 which is substring as well can be defined equivalently in another way also.
Chapter 2 Finite state Automata & Their Languages
Page - -
16
HCT- Department of IT
Formal Language and Automata Theory
Chapter 2 Finite state Automata & Their Languages
Page - -
17
HCT- Department of IT
Formal Language and Automata Theory
2.1.4. Extending Transition function to Strings
(2.1)
Figure 2.3. Transition diagram for the DFA of example 2.2
Chapter 2 Finite state Automata & Their Languages
Page - -
18
HCT- Department of IT
Formal Language and Automata Theory
Example 2.2. Let us design a DFA which accept the language
Chapter 2 Finite state Automata & Their Languages
Page - -
19
HCT- Department of IT
Formal Language and Automata Theory
Figure 2.4 Transition Table for the DFA of example 2.2
2.1.5. The Language of a DFA
Chapter 2 Finite state Automata & Their Languages
Page - -
20
HCT- Department of IT
Formal Language and Automata Theory
2.2. REGULAR EXPRESSIONS AND REGULAR LANGUAGES
Regular expressions are another type of language defining notation. Regular expressions also may be thought of as a programming language, in which we express some important applications such as text-search applications or compiler components. Regular expressions are closely related to nondeterministic finite automata and can be thought of as a user friendly alternative to the NFA notation for describing software components. More details related to Regular expressions are in chapter 4.
2.3 Minimization of DFA
Some DFA states can be redundant. For example following DFA accepts (a|b) +
Figure 2.5 DFA accepts (a|b) +
Figure 2.6 DFA accepts (a|b) +
Chapter 2 Finite state Automata & Their Languages
Page - -
21
HCT- Department of IT
Formal Language and Automata Theory
In above figures 2.5 and 2.6 DFAs are equivalent. State s1 is not necessary. This is a state-minimized (or just minimized) DFA. Every remaining state is necessary. The task of DFA minimization, then, is to automatically transform a given DFA into a stateminimized DFA. Several algorithms and variants are known
For each regular language that can be accepted by a DFA, there exists a DFA with a minimum number of states (and thus a minimum programming effort to create and use) and this DFA is unique (except that states can be given different names. There are three classes of states that can be removed/merged from the original DFA without affecting the language it accepts. Unreachable states are those states that are not reachable from the initial state of the DFA, for any input string. Dead states are those nonaccepting states whose transitions for every input character terminate on themselves. These are also called Trap states because once entered there is no escape. Nondistinguishable states are those that cannot be distinguished from one another for any input string. DFA minimization is usually done in three steps, corresponding to the removal/merger of the relevant states. Since the elimination of nondistinguishable states is computationally the most expensive one, it's usually done as the last step.
DFA Minimization Idea Remove unreachable states, i.e. states which cannot be reached from the start state. Build equivalence classes among states via a fixpoint construction. Two states (q,q') cannot be equivalent if one is a final state and the other is not.
Chapter 2 Finite state Automata & Their Languages
Page - -
22
HCT- Department of IT
Formal Language and Automata Theory
If from (q1,q1') we can reach (q2,q2') via q1 a ! q2 and q1' a ! q2' and we know that (q2,q2') cannot be equivalent, then (q1,q1') cannot be equivalent either.
2.3.1 DFA Minimization Algorithm Recall that a DFA M=(Q, , , q0, F) Two states p and q are distinct if o p in F and q not in F or vice versa, or o for some in , (p, ) and (q, ) are distinct
Using this inductive definition, we can calculate which states are distinct Create lower-triangular table DISTINCT, initially blank For every pair of states (p,q): o If p is final and q is not, or vice versa DISTINCT(p,q) =
Loop until no change for an iteration: o For every pair of states (p,q) and each symbol If DISTINCT(p,q) is blank and DISTINCT( (p,), (q,) ) is not blank DISTINCT(p,q) =
Combine all states that are not distinct
Hopcroft's algorithm One algorithm for merging the nondistinguishable states of a DFA, due to Hopcroft (1971), is based on partition refinement, partitioning the DFA states into groups by their behavior. These groups represent equivalence classes of the MyhillNerode equivalence relation, whereby every two states of the same partition are equivalent if they have the same behavior for all the input sequences. That is, for every two states p1 and p2 that belong to the same equivalence class within the partition P, it will be the case that for every input word w, if one follows the transitions determined by w from the two states p1
Chapter 2 Finite state Automata & Their Languages Page - -
23
HCT- Department of IT
Formal Language and Automata Theory
and p2 one will either be led to accepting states in both cases or be led to rejecting states in both cases; it should not be possible for w to take p1 to an accepting state and p2 to a rejecting state or vice versa.
SUMMARY
GUIDED QUESTIONS
1. Give DFAs accepting following languages over the alphabet {0, 1}:
2. Give DFAs accepting the following languages over the alphabet {0, 1}.
Chapter 2 Finite state Automata & Their Languages
Page - -
24
HCT- Department of IT
Formal Language and Automata Theory
3. Give DFAs accepting the following languages over the alphabet {0, 1}.
REFERENCES
a. Hopcroft J. E., Motwani R, Ullman J.D. Chapter 2 Introduction to Automata Theory, Languages, and Computation, 2nd edition 2001 Addison-Wesley,
Chapter 2 Finite state Automata & Their Languages
Page - -
25