REGULA LANGUAGE PUMPING LEMMA

  100% Pass and No Plagiarism Guaranteed

REGULA LANGUAGE PUMPING LEMMA

Pumping Lemma and NFAs

1. Use the Regular Language Pumping Lemma to prove that the following language is NOT regular.

L = { w | w IS a palindrome. That is, w == wR }

2. Use the Regular Language Pumping lemma to prove that the following language is NOT regular.

L = { aMbN | M > N }

3. Use the Regular language pumping lemma to prove that the following language is NOT regular.

L = { 0N1M0P } | N == M OR N == P }

4. Exactly what is wrong with this “proof” that the following language is NOT regular. Note – the language IS regular and so something had better be wrong with this proof.

L = { aNbMcP | N > 0 AND M > 0 AND P > 0 }

“Proof” : Let K be the constant guaranteed by the pumping lemma. Consider a word w = aKbKcK which is an element of L. The pumping lemma tells us that we can decompose w into xyz such that |xy|= 1. This means that the y component must appear in the first K symbols of w. In our case, it must appear among the initial block of a’s. The pumping lemma also tells us that xyiz must also be in L for all i >= 0. So let us consider xy0z == xz == aK-|y|bKcK which is not in L and thus our assumption that L is regular must be false.

5. Construct an NFA (non-deterministic finite automata) using JFLAP which recognizes the following language. L = { w | w is a string built from the following alphabet and the last digit in the string w HAS appeared previously in the string. For example, 2322453 IS in the language L since the 3 has appeared earlier in the string. However, 22423532437 is NOT in L since the 7 has not appeared previously in the string.

6. Build an NFA (using JFLAP) for the language L = { w | w contains the substring 11010 or the substring 11100 or the substring 11101 }

7. Build an NFA equivalent to the following regular expression.
001( 00 + 11 )* + (01)*011