The Idea of Thompson’s Construction Choice among alternatives: To construct an nfa equal to rIs To add a new start state and a new accepting state and connected them as shown usinge-transitions Clearly, this machine accepts the language L(rs FL(TUL (s), and so corresponds to the regular expression rlsThe Idea of Thompson’s Construction • Choice among alternatives: To construct an NFA equal to r | s – To add a new start state and a new accepting state and connected them as shown usingε-transitions. – Clearly, this machine accepts the language L(r|s) =L(r )UL ( s), and so corresponds to the regular expression r|s. … r  … s   