Peter Linz Edition 4 Exercise 4.3 Question 26 (Page No. 124)

Question

Let $L=$ {$a^nb^m:n\geq100,m\leq50$}.
(a) Can you use the pumping lemma to show that L is regular?
(b) Can you use the pumping lemma to show that L is not regular?

Explain your answers.

Comments

1. Pumping lemma cannot be used to show that a language is regular , so here to prove whether the language is regular we cannot use pumping lemma.

2. Pumping lemma is a negative check , i.e it is mainly used to show that a language is not regular , so yes here we can use pumping lemma to disprove the regularity of the language .

Here we already know that the language is a regular language , since a finite automata can be constructed for the language .

The DFA will have 151 states.