Lecture 7 (Non-regular Languages), 2/6/17

Concepts, definitions (in italics):

·         There are languages that are not regular

·         Examples of languages that are not regular:

o     0^n1^n over alphabet {0,1} is not regular 

o    WW over alphabet {a,b, …, z} is not regular

·         Closure can also be used to show that a language is not regular

·         How to prove that an infinite language is not regular

·         Use the closure properties of RLs (This only works if we already have a language that we know not to be regular; how do we get our first one?)

·         Use the Pumping Lemma to show that it does not have the RL property

·         Pumping Lemma

If L is an infinite regular language, then:
there exists some number p such that for all w in L of length ≥ p,
w = xyz, where |y| ≥ 1,  |xy| ≤ p and xynz is in L for all n ≥ 0.

·         Proof of pumping lemma: let p be the number of states in the DFA of L, consider a computation for a string of length p

·         Using Pumping Language to show that something is not regular is always a proof by contractiction

o    Assume the given language is regular, follow through, get to a contradiction

o    Example: 0n1n over alphabet {0,1} is not regular

o    Example 2: ww over alphabet {a,b, …, z} is not regular [proven by Pumping Lemma,

choose string ap b ap b]