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.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- patterns automata and regular expressions stanford university
- understanding regular expressions special characters and patterns cisco
- regular expression tutorial by glen mcgregor
- regular expressions for natural language processing
- regular expressions stanford university
- 1 regular expression tutorial
- regular expressions the complete tutorial by jan goyvaerts
- c is evolving university of alaska system
- lecture 11b regular expressions university of washington
- lecture 18 regular expressions cmu school of computer science
Related searches
- common english expressions and idioms
- popular expressions and sayings
- meanings of expressions and sayings
- dictionary of expressions and idioms
- calculator for expressions and equations
- expressions and equations practice
- algebraic expressions and equations practice
- identify equations expressions and inequalities
- expressions and equations practice pdf
- expressions and equations answer key
- regular expressions js
- using regular expressions in java