CS 422 — Automata Theory Fall 2009
CS106 — Compiler Principles and Construction
Fall 2011
Lecture 2 DFA & NFA
MUST FIT
Dr. Liang
DFA & NFA Dr. Zhiyao Liang
1
Some Notions and Notations
An automaton whose output response is limited to a simple “yes” or “no” is called an accepter.
A DFA is an accepter. If the last state is an accept state, the answer is “yes”, otherwise, the answer is “no”.
A more general automaton, capable of producing strings of symbols as output, is called a transducer.
A Turing Machine can print symbols on its tape.
and are used interchangeably to represent an empty string, unless special meanings are defined in some special case.
DFA, two interpretations: deterministic finite automaton/ accepter
NFA: nondeterministic finite automaton/accepter.
DFA & NFA Dr. Zhiyao Liang
2
Extended transition function
Let M = (Q, S, q0, d, A) be an FA. We can define the function d* : Q S * Q as follows:
For any q Q, d* (q, ) = q
For any w S * , a S, and q Q,
d* (q, wa) = d (d* (q, w) , a)
Note that the symbols are read from left to right. So in the string wa, a is the last symbol read.
Note that for a single symbol σ:
*(q, σ) = *(q, σ) = (*(q, ),σ) = (q, σ)
Let M = (Q, S, q0, d, F) be an FA. A string w S* is accepted by M if d*(q0, w) F
L(M) = { w | w is accepted by M}
A language L is regular if and only if L = L(M) for some DFA M.
DFA & NFA Dr. Zhiyao Liang
3
Examples:
Sometimes the pattern of the strings in L(M) is not obvious, like this case.
*(q0, 01) = q1
*(q0, 0110) = q0
DFA & NFA Dr. Zhiyao Liang
4
Example
The transition function can be described as a table?
What is DFA (transition graph) that recognizes
{w | w = a*b}, where = {a, b} ?
DFA & NFA Dr. Zhiyao Liang
5
Example
Find a DFA that recognized the set of all strings on
= {a, b} starting with the prefix ab.
DFA & NFA Dr. Zhiyao Liang
6
Example
Find a DFA that accepts all the strings on {0, 1}, except those containing the substring 001.
DFA & NFA Dr. Zhiyao Liang
7
Example
Show that the language L = {awa : w {a, b}* } is regular
DFA & NFA Dr. Zhiyao Liang
8
JFLAP Demo
JFLAP is available from
http://www.cs.duke.edu/csed/jflap/jflaptmp/
A JFLAP tutorial is available at
http://www.jflap.org/
DFA & NFA Dr. Zhiyao Liang
9
Example
Show that L2 is regular, where L is just defined in the previous slide, i.e.,
L2 = { aw1aaw2a : w1, w1 {a, b}* }
DFA & NFA Dr. Zhiyao Liang
10
This example suggests that L2, L3 … Ln are all regular. We will see the poof later.
10
Determinism vs. Nondeterminism
Determinism: there is only one computation direction in a certain situation.
Nondeterminism: there can be several computation directions simultaneously, in a certain situation.
Observe that a DFA has the following features:
A state q can only reach a single state upon reading a certain symbol.
From a state q there is an edge for each symbol in .
We can design a FA where these restrictions are not required.
DFA & NFA Dr. Zhiyao Liang
11
NFA
An non-deterministic finite accepter or NFA, is defined by the quintuple:
M = (Q, , , q0, F)
Q is a finite, nonempty set of states
S is a finite set of input symbols called alphabet
d: Q (S {}) 2Q is the transition function
q0 Q is the initial state
F Q is a set of final or “accepting” states
DFA & NFA Dr. Zhiyao Liang
12
Differences between a DFA and an NFA:
In an NFA, the range of is in the power set of Q (the set of subsets of Q, instead of just Q), so that from the current state, upon reading a symbol, a set of states can be reached simultaneously.
In an NFA, from a state q, no state may be defined as the next state upon reading a symbol. E.g., (q, a) = .
In an NFA, a -move is possible; that is, if there is a -edge from q to q’,
a transition from q to q’ can occur without reading a symbol,
or equivalently, when q is reached, simultaneously q’ is reached.
DFA & NFA Dr. Zhiyao Liang
13
NFA Example
It is an NFA, since there are two transitions labeled with a out of q0 .
DFA & NFA Dr. Zhiyao Liang
14
NFA example
*(q0,a) = {q1, q2}
*(q0,aa) = {q3, q0}
*(q0,aaa) = {q0,q1,q2,q3}
A configuration is defined by a pair (q, w), where q is one current alive state, and w is the string of symbols that have been read
When aaa is read, there are 4 alive configurations
DFA & NFA Dr. Zhiyao Liang
15
JFLAP Demo
At the beginning, no symbol is read.
Figure 02.09:
DFA & NFA Dr. Zhiyao Liang
16
JFLAP Demo
When a is read.
DFA & NFA Dr. Zhiyao Liang
17
JFLAP Demo
When aa is read. The read configuration is dead.
DFA & NFA Dr. Zhiyao Liang
18
JFLAP Demo
When aaa is read. The dead configuration is removed.
DFA & NFA Dr. Zhiyao Liang
19
L(M)
For an NFA, the extended transition function * is defined so that *(q, w) contains q’ if and only if there is walk in the transition graph from q to q’ where the sequence of edges are labeled with the sequence of symbols in w.
Note that the -edges always allowed in the walk.
We can have a formal definition of *.
The language L accepted by an NFA M = (Q, , , q0, F) is defined as
L(M) = {w * : δ* (q0, w) F }
DFA & NFA Dr. Zhiyao Liang
20
Example, what is L(M)?
a
L(M) = {(10)n : n 0 }
δ* (q0, 110) =
DFA & NFA Dr. Zhiyao Liang
21
Why Nondeterminism?
Nowadays digital computers are completely deterministic
A state is uniquely predictable from the input.
Nondeterminism is a valid thinking model.
nondeterminism can be implemented using a deterministic machine by search-and-backtrack is used.
Nondeterminism is convenient for description.
For a NFA, its equivalent DFA can be much more complex.
DFA & NFA Dr. Zhiyao Liang
22
Exercise
Give a set notation description of the language accepted by the automaton depicted in the following diagram. Give a simple verbal characterization of the language.
DFA & NFA Dr. Zhiyao Liang
23
Exercises
Find an NFA with three states that accepts the language
L = {an : n 1 } { bmak : m 0, k 0}
(b) Do you think L can be accepted by an NFA with fewer than three states?
Find an NFA with four states for
L = {an : n 0 } { bna : n 1}.
DFA & NFA Dr. Zhiyao Liang
24
Acknowledgement
Some figures are obtained from the instructor’s resources of the textbook “An Introduction to Formal Languages and Automata”, written by Peter Linz.
These slides are solely created for the teaching purpose of the course Automata Theory.
DFA & NFA Dr. Zhiyao Liang
25
/docProps/thumbnail.jpeg