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

Concepts, definitions (in italics):

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

o    Show how these proofs would look

o    Example:: 02k 13m 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

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




·         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