Class Notes (860,433)
CA (521,022)
McMaster (40,406)
SFWRENG (67)
N A (3)
Lecture 4

SFWRENG 2FA3 Lecture 4: Lecture 2013-04-02
Premium

3 Pages
63 Views

Department
Software Engineering
Course Code
SFWRENG 2FA3
Professor
N A

This preview shows page 1. Sign up to view the full 3 pages of the document.
Description
The properties of regular languages: Closure Properties , ,*, , reverse Regular language: a language, A, is regular if and only if an FSA, μ,ϵ, such that L(μ) = A Membership Algorithm: for a language, A, an algorithm, Alg, is a membership algorithm for A, such that for all ωϵΣ* if ωϵA => Yes 0.ω => Types of languages:  Computable  Algorithic  Recursive  Decidable The limitation FSA Their Working memory is Finite. Our working memory in FSAs is the set of states. Alternative textbook: Linz n n A= a b |n   This cannot be a regular language , A  * Pimping lemma We need a theorem The Pumping lemma: if an infinite language, A, is regular, k  0 x, y,z* x yz A y  k u,v,w* y  uvw i  0 si xuvwz A Applications of the pumping lemma: to prove that a given language is Contradiction method n m A   b |n m ←No limitation on n. Prove that A is not regular. 1 ≤ n < ∞ ← A  a |n  0
More Less
Unlock Document
Subscribers Only

Only page 1 are available for preview. Some parts have been intentionally blurred.

Unlock Document
Subscribers Only
You're Reading a Preview

Unlock to view full version

Unlock Document
Subscribers Only

Log In


OR

Don't have an account?

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