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

Algorithms for Regular Languages

2 Pages
91 Views
Unlock Document

Department
Computer Science
Course
CPSC 313
Professor
Philipp Woelfel
Semester
Summer

Description
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


OR

Join OneClass

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

Sign up

Join to view


OR

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.


Submit