Regular Pumping Lemma

115 Views Asked by At

$$\begin{align*} L&=\left\{b^5w:w\in\{a,b\}^*,\big(2n_a(w)+5n_b(w)\big)\bmod 3=0\right\}\\ L&=\left\{(ab)^na^k:n>k,k\ge 0\right\} \end{align*}$$

Determine if each language is regular or not-regular. The former justied by providing a minimal DFA which accepts the said language and the latter by using the Pumping Lemma for Regular Expressions. Please help. Thanks :)

1

There are 1 best solutions below

0
On

HINT: For the first question, show that the expression $2n_a(w)+5n_b(w)$ increases by $2$ modulo $3$ for each letter of $w$. Thus, it will cycle repeatedly through the numbers $0,2,1$ in that order. Three states will suffice to take care of that, and taking care of the initial $b^5$ is very straightforward.

For the second question, if $p$ is the pumping length, consider the word $(ab)^pa^{p-1}$. You’ll have to consider more than one case, and you’ll want to remember that you can pump down as well as up.