**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

*(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-regularEx: 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 *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:
0^{n}1^{n}
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 **a**^{p}
**b**
**a**^{p}
**b**]

**Reading:**

Section 1.4 (make sure to study the examples)

**Skills:**

Know new definitions, understand new concepts and proofs

Understand the Pumping Lemma and how we derived it.

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.