Question

6.[15 points] Recall the pumping lemma for regular languages: Theorem: For every regular language L, there exists a pumping length p such that, if s€Lwith s 2 p, then we can write s xyz with (i) xy'z E L for each i 2 0, (ii) ly > 0, and (iii) kyl Sp. Prove that A ={a3"b"c?" | n 2 0 } is not a regular language. S=

Answer 1

Follow these steps:

Let LL be a regular language. Then there exists an integer n≥1n≥1 (depending only on LL) such that every string ww in LL of length at least nn (pp is called the "pumping length") can be written as w=xyzw=xyz (i.e., ww can be divided into three substrings), satisfying the following conditions:

1. |y|≥1|y|≥1
2. |xy|≤n|xy|≤n and
3. a "pumped" ww is still in LL: for all i≥0i≥0, xyiz∈Lxyiz∈L.

Assume that you are given some language LL and you want to show that it is not regular via the pumping lemma. The proof looks like this:

1. Assume that LL is regular.
2. If it is regular, then the pumping lemma says that there exists some number nn which is the pumping length.
3. Pick a specific word w∈Lw∈L of length larger than nn. The difficult part is to know which word to take.
4. Consider ALL the ways to partition ww into 3 parts, w=xyzw=xyz, with |xy|≤n|xy|≤n and yy non empty. For each of these ways, show that it cannot be pumped: there always exists some i≥0i≥0 such that xyiz∉Lxyiz∉L.
5. Conclude: the word ww cannot be "pumped" (no matter how we split it to xyzxyz) in contradiction to the pumping lemma, i.e., our assumption (step 1) is wrong: LL is not regular.