Question

Use the pumping lemma to show that the following language is non-regular: [a"b2n,n> 1) 1) usually we need to find a word in the language as an example, what length of the word we should use as the example? what are the three possible ways to choose substring y in the pumping lemma? if a language satisfy the pumping lemma, is this language a regular language? Why?

Answer 1

Friday 47 324-04 ukpbefu叩ing length ASIK This does nok belorg to L.

The pumping lemma is proved by using pigeon hole principle. If any language L is regular, then we should be able to produce a DFA for L. Now DFA has a finite number of states, let the number of states be p.

Now for any string in the language, we get a sequence of states traversed before the string is accepted. Now if we take a string greater than length p, by pigeon hole principle some state must be repeated again in the sequence. Therefore there is a cycle in the DFA. So we divide the string in to x,y,z such that y is the string accepted by the cycle.

From that we derive the principles:

1) for each i>=0 x(y^i)z belong to L. As y is covered by a cycle in DFA, it doesn't matter how many times the string y is repeated.

2) xy covered once should be less than the number of states. As covering x and y should not repeat any state.

3) The length of string y should be greater than 0. Because there is a cycle.