Class Notes (837,360)
Canada (510,237)
CPSC 313 (6)

Algorithms for Regular Languages

2 Pages
Unlock Document

Computer Science
CPSC 313
Philipp Woelfel

January 27th, 2012 Algorithms for Regular Languages Theorem 3.1 - Given L in standard representation and w 2 ▯ , there is an algorithm for determining whether w 2 L. Proof. 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 6= ; , 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. ▯ Theorem 3.3 - There exists an algorithm for determining whether two regular languages L 1L 2 given in a standard representation, are equal. Proof. Let M ie a DFA for L , i 2 f1;2g. Let L = (L 1 L )2_ (L ^1L ).2 Then L = L , L = ;. 1 2 Using the constructions from the proof of Threorem ??, we construct an NFA N for L. Convert N into an equivalent DFA M. We can use this DFA to show the algorithm exists. ▯ Context-Free Languages Regular languages are not powerful enough to describe languages such as pro- gramming languages. E:g:: A syntactically correct p
More Less

Related notes for CPSC 313

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.