OutlineUsing Regular ExpressionsLanguage SyntaxNFA to DFASubset ConstructionExample 1Example 2RE to NFAConversion with WidgetsConversion ExampleActivityOutlineUsing Regular ExpressionsNFA to DFARE to NFAActivityCS421 Lecture 10: Converting RegularExpressions to DFAs1Mark [email protected] of Illinois at Urbana-ChampaignJune 26, 20061Based on slides by Mattox Beckman, as updated by Vikram Adve, GulAgha, and Elsa GunterMark Hills CS421 Lecture 10: Converting Regular Expressions to DFAsOutlineUsing Regular ExpressionsNFA to DFARE to NFAActivityUsing Regular ExpressionsNFA to DFARE to NFAActivityMark Hills CS421 Lecture 10: Converting Regular Expressions to DFAsOutlineUsing Regular ExpressionsNFA to DFARE to NFAActivityLanguage SyntaxUsing Regular ExpressionsWe’ve se en that regular expressions have nice descriptiveproperties, providing a convenient way to specify syntax. We’vealso seen that finite automata provide a nice model for matchingstrings, providing small “machines” tuned to match strings. Howcan we leverage the nice characteristics of both for recognizinglanguage syntax?◮First, convert regular expressions to NFAs, since there is anice, direct conversion from REs to NFAs◮Second, convert NFAs to DFAs, since they provide equivalentcomputational power and since DFAs have a nicercomputational model (no backtracking needed)Mark Hills CS421 Lecture 10: Converting Regular Expressions to DFAsOutlineUsing Regular ExpressionsNFA to DFARE to NFAActivitySubset ConstructionExample 1Example 2Subset ConstructionTo convert from an NFA to a DFA, we somehow need to accountfor mul tiple paths with the same label.◮Key Concept: All states reachable in NFA along a given pathshould be same state in DFA◮DFA states will thus be subsets of set of NFA statesMark Hills CS421 Lecture 10: Converting Regular Expressions to DFAsOutlineUsing Regular ExpressionsNFA to DFARE to NFAActivitySubset ConstructionExample 1Example 2ǫ ClosureAlso, we don’t have ǫ in DFAs – how do we eliminate this?◮The ǫ closure S (ǫ) of S, a se t of states, is the smallest set◮containing S◮for all s ∈ S and all states t, if (s, ǫ, t) is an edge then t ∈ SMark Hills CS421 Lecture 10: Converting Regular Expressions to DFAsOutlineUsing Regular ExpressionsNFA to DFARE to NFAActivitySubset ConstructionExample 1Example 2Reachable StatesFor any letter α ∈ Σ, with Σ the alphabet, the α reachable statesfrom S , S (α), are defined as:S(α) = {t | (s, α, t) an edge for some s ∈ S }◮Key Intuition: To figure out where we can get to from a setof states when given a character from the alphabet, find allstates with an incoming edge labeled with the character andcoming from some state i n the setMark Hills CS421 Lecture 10: Converting Regular Expressions to DFAsOutlineUsing Regular ExpressionsNFA to DFARE to NFAActivitySubset ConstructionExample 1Example 2Performing the Subset Construction◮Begin with S = {s0}(ǫ), the ǫ-closure of the set containingjust the NFA start state – this is our DFA start state◮While our states keep changing◮for each new state S and letter α, add state S (α)(ǫ), the ǫclosure of all states α-reachable from S◮add edge (S , α, S (α)(ǫ))◮Mark as final states any set of states in the DFA containing afinal state from the N FAAny problems?◮Potentially exponential in the number of NFA statesMark Hills CS421 Lecture 10: Converting Regular Expressions to DFAsOutlineUsing Regular ExpressionsNFA to DFARE to NFAActivitySubset ConstructionExample 1Example 2Example 1A B011Mark Hills CS421 Lecture 10: Converting Regular Expressions to DFAsOutlineUsing Regular ExpressionsNFA to DFARE to NFAActivitySubset ConstructionExample 1Example 2Example 1A B101New states: {A}New edges:Mark Hills CS421 Lecture 10: Converting Regular Expressions to DFAsOutlineUsing Regular ExpressionsNFA to DFARE to NFAActivitySubset ConstructionExample 1Example 2Example 1A B101New states: {A}New edges: ({A}, 0, ), ({A}, 1, )Mark Hills CS421 Lecture 10: Converting Regular Expressions to DFAsOutlineUsing Regular ExpressionsNFA to DFARE to NFAActivitySubset ConstructionExample 1Example 2Example 1A B110New states: {A}New edges: ({A}, 0, {A}), ({A}, 1, )Mark Hills CS421 Lecture 10: Converting Regular Expressions to DFAsOutlineUsing Regular ExpressionsNFA to DFARE to NFAActivitySubset ConstructionExample 1Example 2Example 1A B011New states: {A}New edges: ({A}, 0, {A}), ({A}, 1, {A, B})Mark Hills CS421 Lecture 10: Converting Regular Expressions to DFAsOutlineUsing Regular ExpressionsNFA to DFARE to NFAActivitySubset ConstructionExample 1Example 2Example 1A B011New states: {A}, {A, B }New edges:({A}, 0, {A}), ({A}, 1, {A, B }), ({A, B}, 0, ), ({A, B}, 1, )Mark Hills CS421 Lecture 10: Converting Regular Expressions to DFAsOutlineUsing Regular ExpressionsNFA to DFARE to NFAActivitySubset ConstructionExample 1Example 2Example 1A B110New states: {A}, {A, B }New edges:({A}, 0, {A}), ({A}, 1, {A, B }), ({A, B}, 0, {A}), ({A, B}, 1, )Mark Hills CS421 Lecture 10: Converting Regular Expressions to DFAsOutlineUsing Regular ExpressionsNFA to DFARE to NFAActivitySubset ConstructionExample 1Example 2Example 1A B011New states: {A}, {A, B }New edges:({A}, 0, {A}), ({A}, 1, {A, B }), ({A, B}, 0, {A}), ({A, B}, 1, {A, B})Mark Hills CS421 Lecture 10: Converting Regular Expressions to DFAsOutlineUsing Regular ExpressionsNFA to DFARE to NFAActivitySubset ConstructionExample 1Example 2Example 1A B011New states: {A},{A, B }New edges:({A}, 0, {A}), ({A}, 1, {A, B }), ({A, B}, 0, {A}), ({A, B}, 1, {A, B})Final states: {A, B}Mark Hills CS421 Lecture 10: Converting Regular Expressions to DFAsOutlineUsing Regular ExpressionsNFA to DFARE to NFAActivitySubset ConstructionExample 1Example 2Example 1{A}{A, B}0110New states: {A}, {A, B }New edges:({A}, 0, {A}), ({A}, 1, {A, B }), ({A, B}, 0, {A}), ({A, B}, 1, {A, B})Final states: {A, B}Mark Hills CS421 Lecture 10: Converting Regular Expressions to DFAsOutlineUsing Regular ExpressionsNFA to DFARE to NFAActivitySubset ConstructionExample 1Example 2Example 2A B01ǫ0Mark Hills CS421 Lecture 10: Converting Regular Expressions to DFAsOutlineUsing Regular ExpressionsNFA to DFARE to NFAActivitySubset ConstructionExample 1Example 2Example 2A B010ǫNew states: {A}(ǫ) = {A, B}New edges: ({A, B}, 0, ), ({A, B}, 1, )Mark Hills CS421 Lecture 10: Converting Regular Expressions to DFAsOutlineUsing Regular ExpressionsNFA to DFARE to NFAActivitySubset ConstructionExample 1Example 2Example
View Full Document