The Idea of Thompson’s Construction Repetition: Given a machine that corresponds to r Construct a machine that corresponds to ro To add two new states, a start state and an accepting state The repetition is afforded by the newe-transition from the accepting state of the machine of r to its start state To draw an e-transition from the new start state to the new accepting state This construction is not unique, sim-plifications are possible in the many cases
The Idea of Thompson’s Construction • Repetition: Given a machine that corresponds to r， Construct a machine that corresponds to r* – To add two new states, a start state and an accepting state. – The repetition is afforded by the newε-transition from the accepting state of the machine of r to its start state. – To draw an ε-transition from the new start state to the new accepting state. – This construction is not unique, sim-plifications are possible in the many cases. … r
Examples of NFAs construction Example 1. 12: Translate regular expression abla into NFA )
Examples of NFAs Construction Example 1.12: Translate regular expression ab|a into NFA a b a b a b a
Examples of NFAs construction Example 1. 13: Translate regular expression letter(letter digit *into NFA letter letter letter letter letter letter letter RET
Examples of NFAs Construction Example 1.13: Translate regular expression letter(letter|digit)* into NFA letter digit letter letter letter letter letter letter letter RET
2.4.2 From an nfa to a dfa
2.4.2 From an NFA to a DFA
Goal and methods ·Goal Given an arbitrary NFA, construct an equivalent DFA(ie,one that accepts precisely the same strings) Some methods (1)Eliminating s-transitions E-closure: the set of all states reachable by -transitions from a state or states (2)Eliminating multiple transitions from a state on a single input character Keeping track of the set of states that are reachable by matching a single character Both these processes lead us to consider sets of states instead of single states. Thus, it is not surprising that the DFa we construct has sets of states of the original nfa as its states
Goal and Methods • Goal – Given an arbitrary NFA, construct an equivalent DFA. (i.e., one that accepts precisely the same strings) • Some methods – (1) Eliminating -transitions • -closure: the set of all states reachable by -transitions from a state or states – (2) Eliminating multiple transitions from a state on a single input character. • Keeping track of the set of states that are reachable by matching a single character – Both these processes lead us to consider sets of states instead of single states. Thus, it is not surprising that the DFA we construct has sets of states of the original NFA as its states