OutlineUsing 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 N FAActivityMark Hills CS421 Lecture 10: Converting Regular Expressions to DFAsOutlineUsing Regular ExpressionsNFA to DFARE to NFAActivityLanguage SyntaxUsing Regular ExpressionsWe’ve seen that regular expressions have nice descriptiveproperties, providing a conveni ent 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 p ower and since DFAs have a nicercomputational mo del (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 multiple paths with the same label.◮Key Concept: All states reachable in NFA along a given pathshould b e same s tate 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 ǫ c losure 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 lab ele d with the character andcoming from s ome state in 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 ǫ-cl osure of the set containingjust the N FA start state – this is our DFA start state◮While our s tates 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 i n 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 2A B100ǫNew states: {A, B}New edges: ({A, B }, 0, {A}(ǫ)), ({A, B}, 1, )Mark Hills CS421 Lecture 10: Converting Regular
View Full Document
Unlocking...