Lecture 23: NFAs, Regular expressions, and NFA DFA

[Pages:43]CSE 311: Foundations of Computing

Lecture 23: NFAs, Regular expressions, and NFADFA

Last time: Nondeterministic Finite Automata (NFA)

? Graph with start state, final states, edges labeled by symbols (like DFA) but

? Not required to have exactly 1 edge out of each state labeled by each symbol--- can have 0 or >1

? Also can have edges labeled by empty string

? Defn: x is in the language recognized by an NFA if and only if x labels a path from the start state to some final state

1

1

1

s0

s1

s2

s3

0,1

0,1

Last time: Three ways of thinking about NFAs

? Outside observer: Is there a path labeled by x from the start state to some final state?

? Perfect guesser: The NFA has input x and whenever there is a choice of what to do it magically guesses a good one (if one exists)

? Parallel exploration: The NFA computation runs all possible computations on x step-by-step at the same time in parallel

Last time: Compare with the smallest DFA

0,1

1

s3

0,1

s2

0,1

s1

s0

001

1

0

0 000

1

010

0

0

100

1

011

1

1

1

101

0

111 1

0

1

0

110 0

Parallel Exploration view of an NFA

0,1

1

s3

0,1

s2

0,1

s1

s0

Input string 0101100

010110

s3

s3

s3

s3

s3

s3

s2

s2

s1

s2

s1

s0 X

0

s3

s3

s1

s0

s0 X

NFAs and regular expressions

Theorem: For any set of strings (language) described by a regular expression, there is an NFA that recognizes .

Proof idea: Structural induction based on the recursive definition of regular expressions...

Regular Expressions over

? Basis:

? , are regular expressions ? a is a regular expression for any a

? Recursive step:

? If A and B are regular expressions then so are: (A B) (AB) A*

Base Case ? Case :

? Case : ? Case a:

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download