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
