- Exam 1
- Scheduled for next Wednesday (Feb. 17)
- Covers material on finite automata and regular languages
- Might logically fit better on Monday, Feb. 15
- Which do you prefer?
- Problem set question 2: regular expressions for languages in 1.6a and 1.6e
- Section 1.4
- Motivation for way to prove non-regularity
- Pumping lemma
- Sufficiently long substrings imply regular…?
- More precisely… If L is regular, then sufficiently long strings in L are “pumpable”
- “Pumpable” = string w has 3 parts x, y , z, i.e., w = xyz, and y
can be “pumped” back into string, i.e., xyiz is in L
- And |y| > 0, y non-empty
- |xy| ≤ p
- p = pumping length
- “Sufficiently long” w means |w| ≥ p
- What about all 1-symbol strings over some alphabet?
- Pumping lemma holds vacuously
- Converse (if L is pumpable, then L is regular) is not generally true
- Examples
- Set of strings over { (, ) } in which the parentheses are balanced is not regular
- Notice s = (p)p = xyz is in L
- |s| > p
- |xy| ≤ p implies y = (k
- xyiz has to be unbalanced, i.e., not in L, for all i ≠ 1
- Contradiction! Since we implicitly assumed L to be regular at the beginning, and everything else followed from that assumption, L must not be regular after all
- Set of strings over { (, ) } in which the parentheses are balanced is not regular
- More examples
- Mini-assignment: show that the set of postfix arithmetic expressions over some
simple alphabet (e.g., +, -, ×, /, and 1-digit numbers) is not regular
- Google what “postfix” arithmetic is if you need to