Sipser: Section 1.4

From CSWiki

CSC 341: Front Door

---

Nonregular Language

The Pumping Lemma (page 78)

 If A is a regular language, then there exists a natural number p (the
 pumping length) such that, if s is any string in A of length at least
 p, then s may be divided into three pieces, s = xyz,
 such that:
  1. for each i0, xyi z  A,
  2. |y| >0, and
  3. |xy|  p
  
 Note: |s| represents the length of string s, yi means that i copies of y are
 concatenated.

Proof Strategies:

• In order to prove that a language is regular, we can
  • construct a FA (either DFA or NFA) that recognizes the language and apply Definition 1.16 or Corollary 1.40, or
  • show that the language is the union of two languages that are already known to be regular and apply Theorem 1.45, or
  • show that the language is the concatenation of two languages that are already known to be regular and apply Theorem 1.47, or
  • show that the language is the star of a language that is already known to be regular and apply Theorem 1.49, or
  • construct a regular expression that represents the language and apply Theorem 1.54.

• In order to prove that a language is nonregular, assume that the language is regular and show that this assumption leads to a contradiction, using the pumping lemma.

Misunderstandings

Q: If n is the length of a string, why (pg. 78) is the associated sequence of states of length n + 1?

A: Consider that between any two nodes, there can exist but one direct link. If we have a path that goes from node 1, through node 2, and on to node 3, that path is of length two. The string of length n represents this path of transitions (as each symbol of the string is an input symbol), while the sequence of states equals the number of nodes this path travels through. In other words, the string shows the path "in-between" the states, and must therefore be one less than the total number of states.

---

CSC 341: Front Door