CPSC 313 Lecture : Algorithms for Regular Languages

70 views2 pages

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.

Get access

Grade+20% off
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers

Related Documents