Copyright (C) 2015, H. Conrad Cunningham
Acknowledgements: These lecture notes are for use with Chapter 2 of the textbook: Peter Linz. Introduction to Formal Languages and Automata, Fifth Edition, Jones and Bartlett Learning, 2012. The terminology and notation used in these notes are similar to those used in the Linz textbook. This document uses several figures from the Linz textbook.
Advisory: The HTML version of this document requires use of a browser that supports the display of MathML. A good choice as of December 2015 seems to be a recent version of Firefox from Mozilla.
In chapter 2, we approach automata and languages more precisely and formally than in chapter 1.
A finite automaton is an automaton that has no temporary storage (and, like all automata we consider in this course, a finite number of states and input alphabet).
Linz Definition (DFA): A deterministic finite accepter, or dfa, is defined by the tuple where
Q is a finite set of internal states
is a finite set of symbols called the input alphabet
is a total function called the transition function
is the initial state.
is a set of final states.
currentState :=
To visualize a dfa, we use a transition graph constructed as follows:
The graph pictured in Linz Figure 2.1 represents the dfa , where is represented by
,
,
,
Note that is the initial state and is the only final state in this dfa.
The dfa in Linz Figure 2.1:
What about 0111? 1100?
Linz Definition: The extended transition function is defined recursively:
The extended transition function gives the state of the automaton after reading a string.
Linz Definition 2.2 (Language Accepted by DFA): The language accepted by a dfa is .
That is, is the set of all strings on the input alphabet accepted by automaton M.
Note that above and are total functions (i.e., defined for all strings).
The automaton in Linz Figure 2.2 accepts all strings consisting of arbitrary numbers of 's followed by a single .
In set notation, the language accepted by the automaton is .
Note that has two self-loop edges, each with a different label. We write this compactly with multiple labels.
A trap state is a state from which the automaton can never "escape".
Note that is a trap state in the dfa transition graph shown in Linz Figure 2.2.
Transition graphs are quite convenient for understanding finite automata.
For other purposes--such as representing finite automata in programs--a tabular representation of transition function may also be convenient (as shown in Linz Fig. 2.3).
Find a deterministic finite accepter that recognizes the set of all string on starting with the prefix .
Linz Figure 2.4 shows a transition graph for a dfa for this example.
The dfa must accept and then continue until the string ends.
This dfa has a final trap state (accepts) and a non-final trap state (rejects).
Find a dfa that accepts all strings on , except those containing the substring .
need to "remember" whether last two inputs were
use state changes for "memory"
Linz Figure 2.5 shows a dfa for this example.
Accepts: , 0, 00, 01, 010000
Rejects: 001, 000001, 0010101010101
Linz Definition 2.3 (Regular Language): A language L is called regular if and only if there exists a dfa M such that .
Thus dfas define the family of languages called regular.
Show that the language is regular.
Construct a dfa.
Check whether begin/end with "a".
Am in final state when second a input.
Linz Figure 2.6 shows a dfa for this example.
Question: How would we prove that a languages is not regular?
We will come back to this question in chapter 4.
Let be the language in the previous example (Linz Example 2.5).
Show that is regular.
.
Construct a dfa.
Use Example 2.5 dfa as starting point.
Accept two consecutive strings of form .
Note that any two consecutive 's could start a second string.
Linz Figure 2.7 shows a dfa for this example.
The last example suggests the conjecture that if a language then so is , , etc.
We will come back to this issue in chapter 4.
Linz Definition 2.4 (NFA): A nondeterministic finite accepter or nfa is defined by the tuple where , , , and are defined as for deterministic finite accepters, but
.
Remember for dfas:
Q is a finite set of internal states.
is a finite set of symbols called the input alphabet.
is the initial state.
is a set of final states.
The key differences between dfas and nfas are
dfa: yields a single state
nfa: yields a set of states
dfa: consumes input on each move
nfa: can move without input ()
dfa: moves for all inputs in all states
nfa: some situations have no defined moves
An nfa accepts a string if some possible sequence of moves ends in a final state.
An nfa rejects a string if no possible sequence of moves ends in a final state.
Consider the transition graph shown in Linz Figure 2.8.
Note the nondeterminism in state with two possible transitions for input .
Also state has no transition for any input.
Consider the transition graph for an nfa shown in Linz Figure 2.9.
Note the nondeterminism and the -transition.
Note: Here means the move takes place without consuming any input symbol. This is different from accepting an empty string.
Transitions:
for ?
for ?
for ?
for ?
Accepts: , 10, 1010, 101010
Rejects: 0, 11
As with dfas, the transition function can be extended so its second argument is a string.
Requirement: where is the set of all possible states the automaton may be in, having started in state and read string .
Linz Definition (Extended Transition Function): For an nfa, the extended transition function is defined so that contains if there is a walk in the transition graph from to labelled .
Linz Definition 2.6 (Language Accepted by NFA): The language accepted by the nfa is defined
.
That is, is the set of all strings for which there is a walk labeled from the initial vertex of the transition graph to some final vertex.
Let's again examine the automaton given in Linz Figure 2.9 (Example 2.8).
This nfa, call it :
must end in
Note that is a dead configuration because .
When computers are deterministic?
an nfa can model a search or backtracking algorithm
nfa solutions may be simpler than dfa solutions (can convert from nfa to dfa)
nondeterminism may model externally influenced interactions (or abstract more detailed computations)
When are two mechanisms (e.g., programs) equivalent?
When they have exactly the same descriptions?
When they always go through the exact same sequence of steps?
When the same input generates the same output for both?
The last seems to be the best approach.
Linz Definition 2.7 (DFA-NFA Equivalence): Two finite accepters and are said to be equivalent if . That is, if they both accept the same language.
Here "same language" refers to the input and "both accept" refers to the output.
Often there are many accepters for a language.
Thus there are many equivalent dfa and nfas.
Again consider the nfa represented by the graph in Linz Fig. 2.9. Call this .