Covers material on finite automata and regular languages (e.g., DFAs, NFAs,
regular expressions, equivalance and similar proofs, non-regularity and its
proofs, etc.)
3 - 5 short-answer questions
Full class period
Open book, notes, computer for reference; closed person
Questions?
Non-Regular Language Proofs
Can finite automata “do math”?
axbycx+y = language A
e.g., aabbbccccc
But not abbcc
Let s = apbcp+1 (represents p + 1 = p+1)
s = xyz, y must be ak k ≥ 1
xyiz = ap+(i-1)kbcp (represents p+(i-1)k + 1 = p+1,
untrue for i ≥ 2)
{ w ∈ {a,b,c}* | w is not of the form axbycx+y }
= language B
= complement of A (A′)
Set of regular languages closed under complement
If B were regular, B′ = A would be regular
But A not regular
Corollary to set of regular languages being closed under complement: L is regular iff
L′ is regular
Another standard example of using closure properties to prove non-regularity:
{ w ∈ {a,b}* | number of a’s = number of b’s } = language C
C ∩ (a*b*) = anbn which is non-regular
axbf(x) where f is increasing (i.e., x > y iff f(x) > f(y))
Notice that axbx not regular but is an instance of this family
Let s = apbf(p)
Pumping yields ap+kbf(p), but f(p+k) ≠ f(p)
HTML/XML (possibly nested strings of the form <tag> text </tag>)
Not regular
Regular languages can’t ensure that opening and closing tags balance; generalization
of balanced parentheses example
Is English regular?
No, e.g., finite automata can’t remember gender agreement between
a noun and a pronoun across an arbitrarily long string of adjectives