Computer Science 3331A/B Chapter Notes - Chapter 9: Regular Expression, Flight Controller, Concatenation

• School: Western University
• Department: Computer Science
• Course: Computer Science 3331A/B
• Professor: Lucian Ilie

Document Summary

Simulate ndfsm and see if the machine accepts w. if yes, return true. If from regular expression, regextofsm, then simulate ndfsm on that. Graph analysis approach: mark states reachable from start state via some path. If any of the marked states are accepting, return false, else return true. In other words if there exists some reachable accepting state. Simulation approach: make a dfsm from ndfsm m, called m", for all w in * such that |w| < |kofm| do, decidefsm(m",w) this runs ndfsm simulation and returns whether that bitch accepts or nah. If m" accepts at least one string return false (not empty), else return true (empty) Yes if the complement of l accepts nothing. Graph analysis: m" = ndfsmtodfsm(m, m""= mindfsm(m", on path to accepting state, see if any cycles. Equivalent if l(m1) l(m2) orr l(m2) l(m1) = empty set. Construct ma = l(m1) l(m2: mb = l(m2) l(m1, mc = ma orr mb.