SUNY Geneseo, Department of Computer Science

The Pumping Lemma, Part 3

CSci 342, Fall 2001

Prof. Doug Baldwin

Previous Lecture

Misc

Test One a week from today (10/5)

• Practice exam on Web
• Short-answer questions
• Open book, open notes, open laptop (closed net)
• whole class period
• covers regular languages, finite automata

Questions?

Pumping Examples

Prove that the language consisting of all strings of the form x+y=z, where x, y, and z are decimal representations of integers and the sum of the integers represented by x and y equals the integer represented by z, is not regular.

• e.g., 12+5=17, 1+1=2, 195+21=216
  • but not 12=5++17, 1+2=6
• Pick s = 1^p+0=1^p
  • (cut down on number of cases to deal with)
  • e.g., 111+0=111, 11111+0=11111
• Mini-assignment: finish showing that pumping produces strings not in language.
  • Show no matter how 111...11+0=111...11 breaks into u, v, w substrings (s=uvw) subject to pumping lemma restrictions (|uv| <= p, |v| >= 1), uvⁱw is not in language.
  • What are the possible v's (pumpable substrings)?
    • v= "+0"? No, v has to lie within the first p symbols
    • v = 11..11 (i.e., 1ⁿ)
      • Only choice!
  • What happens when we pump, i.e., what makes uvⁱw not in language?
    • Too many 1's on left of "=" to be a correct addition.
      • Started with 1^(p-n)+n+0=1^p
      • Pumping yields 1^(p-n)+ni+0=1^p

General intent: Start with a string in L, after pumping result is not in L

Pumping lemma to prove that L is regular?

• No!
• if L is regular, then strings are pumpable
  • Does Mean: not pumpable -> not regular
  • Does Not Mean: pumpable -> regular

Show that the set of all strings over {a,b} in which the number of a's is greater than the number of b's is not regular

• e.g., ababa, bbabaaaaa, aaaaa, ...
  • but not: abab, b, aabbb, ...
• Pick s = b^pa^p+1
  • The thinking behind this choice: Key characteristic of language is that the number of a's is bigger than the number of b's, see if we can attack that by pumping to produce a string not in the language. This requires some b's to pump, guarantee that by starting our s with p b's. But then to be in the language, we need enough a's to exceed the number of b's, so follow the b's with p+1 a's.
  • s = xyz
  • y = bⁿ i.e., bb...bb
  • xyⁱz is not in language because you now have more b's than a's
• What if s = a^p+1b^p
  • x contains a^p+1?
  • but shouldn't y = aⁿ so x = at best a^p+1-n ?
  • what about |xy| <= p? It requires y to lie within the a's.
  • y = aⁿ, i.e., aaa...aa. This is in fact the only possibility for y.
  • consider xyⁱz, but with i=0, i.e., xz
  • take out n>0 a's (because |y| >= 1)
  • result has no more a's than b's, not in language

Next

Since there exist languages that aren't regular, apparently including interesting and useful languages like HTML, are there ways of describing languages that can handle those languages, and models of computation that can recognize them?

Read Chapter 2 intro and Section 2.1 up to but not including "Chomsky Normal Form" on page 98.

Mini-Assignment: Design a context-free grammar for the language of properly nested and closed <table> and </table> tags. (You need not include any text between the tags, or any other tags.)

Next Lecture