# Homework Help: Pumping Lemma Problem

1. Oct 6, 2008

### needhelp83

Problem:

Consider the languages over the alphabet $$\sum = {a,b}$$ defined by $$L_1 = {a^{k}w|k$$ is the number of consecutive a's at start, w is the rest of the string, and the number of a's in w is greater than or equal to k},

and

$$L_2 = {a^{k}w|k$$ is the number of consecutive a's at start, w is the rest of the string, and the number of a's in w is less than or equal to k},

For language, use pumping lemma to prove that the language is not regular. For each proof, you must state s in terms of the integer p from the pumping lemma, and then explain clearly why some $$xy^{i}z$$ is not in the language specific for i.

ATTEMPTED SOLUTION:
Assume $$L_1$$ is a regular language. If $$s=a^pba^p$$ and $$x=a^p, y=ba^p, and z=\epsilon$$. Using the pumping down method, pump y to i=0. This gives $$a^p$$ which returns a greater amount of a's in x. This is a contradiction, thus $$L_1$$ is not a regular language.

I don't believe this is right. I am really struggling with this pumping and looking for any help I can get. Thanks!
1. The problem statement, all variables and given/known data

2. Relevant equations

3. The attempt at a solution