**Lecture 7 (Non-regular Languages), 9/20/17**

**Concepts, definitions (in italics):**

·
Concept
of *closure *(of a set under an
operation)

- Where the name “closure
property” comes from
- Why regular languages
are closed under union, complement, star, complement, intersection
- How to use closure
property to prove language regular

o Show how these proofs would look

o Example::
0^{2k} 1^{3m} where k, m >= 0

equals the intersection of 0*1* and the language {# 0’s is divisible by 2, # of
1’s divisible by 3}

so it must be regular

·
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

*Contrapositive*of closure property:

*(for binary op)*if L1 op L2 gives a non-regular language (where op is one of the operations under which regular languages are closed), then at least one of L1, L2 must be non-regular. (*for unary op*) if op(L1) gives a non-regular language (where op is one of the operations under which regular languages are closed), then L1 must be non-regular- Ex: suppose we know that
**L = {0**≥^{n }1^{n }: n**0}**is not regular. L is the*intersection*of L1 =**{ {****0, 1}*: # of 0's same as # of 1's}**and L2 =**{0*1***}. We know that L2 is regular; therefore L1 is not regular. - This is a
*proof by contradiction* - 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 xy* ^{n}*z is in L for all

·
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: 0^{n}1^{n}
over alphabet {0,1} is not regular

**Reading:**

- Section 1.4 (make
sure to study the examples)

**Skills:**

- Know new definitions, understand new concepts and
proofs
- Be able to prove the Pumping Lemma
- Be able to apply closure property of RLs to show the
language is not regular
- Be able to apply the Pumping lemma to show that a given
language is not regular

**Notes:**

- For a statement of the form "if A then B",
the
*contrapositive*is "if not B, then not A"; the*converse*is "if not A, then not B”. The contrapositive is equivalent to the original, but the converse is not.

·
The fact that there exist
non-regular languages can be proved by counting

o
*countable* and *uncountable* sets

o
the set of regular languages is
countable – can be proved by enumerating all REs

o using *diagonalization method* to show that the set of
all languages is not countable