Class Notes (923,273)
CA (543,200)
McMaster (43,303)
SFWRENG (131)
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.
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
A=
 
|
nn
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,
0
, , *
, , *
0
i
k
x y z x y z A y k
u v w y u v w
i
s xuvwz A

 
 


Applications of the pumping lemma: to prove that a given language is

#### Loved by over 2.2 million students

Over 90% improved by at least one letter grade.

OneClass has been such a huge help in my studies at UofT especially since I am a transfer student. OneClass is the study buddy I never had before and definitely gives me the extra push to get from a B to an A!

Leah — University of Toronto

Balancing social life With academics can be difficult, that is why I'm so glad that OneClass is out there where I can find the top notes for all of my classes. Now I can be the all-star student I want to be.

Saarim — University of Michigan

As a college student living on a college budget, I love how easy it is to earn gift cards just by submitting my notes.

Jenna — University of Wisconsin

OneClass has allowed me to catch up with my most difficult course! #lifesaver

Anne — University of California
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

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

Unlock Document

Unlock to view full version

Unlock Document
Notes
Practice
Earn
Me

OR

Don't have an account?

Join OneClass

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

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.