CPSC 313 Lecture : Algorithms for Regular Languages
22 Nov 2012
School
Department
Course
Professor
Document Summary
Theorem 3. 1 - given l in standard representation and w , there is an algorithm for determining whether w l. Assume w. l. o. g. that l is given by a dfa m with l(m ) = l. let g(m ) be the state transition graph of m . L (cid:54)= in g(m ) there is a path from the intial state to the nal state. Use depth- rst search to check whether g(m ) has such a path. L is in nite, g(m ) contains a cycle c, and there is a path from the initial state to c and a path from c to a nal state. (cid:3) Theorem 3. 3 - there exists an algorithm for determining whether two regular languages l1, l2, given in a standard representation, are equal. Let mi be a dfa for li, i {1, 2}. Let l = (l1 l2) ( l1 l2). ?, we construct an nfa n for l.
