# Is this language L regular?

Let's say we have the language L = {w $$\in$$ {a,b}$$^*$$ : ($$\exists n \in \mathbb{N}$$)[$$w|_b = 5^n$$]}. I want to know if this is a regular language or not. How do I go about doing this? I'm familiar with the Myhill-Nerode theorem but I don't know how to apply it.

• – D.W.
Jun 10 '20 at 22:19

You don't need the Myhill-Nerode theorem. Suppose that $$L$$ was regular and let $$c>0$$ be its pumping length.

The word $$b^{5^c}$$ is in $$L$$ and therefore there is some positive constant $$k \le c < 5^c$$ such that $$b^{5^c + ik} \in L$$ for all integer values of $$i \ge -1$$. For $$i =1$$ you must have $$b^{5^c + k} \in L$$ which implies that $$5^{c} + k$$ is a power of $$5$$.

This is a contradiction since $$5^ c < 5^c + k < 5^c + 5^c = 2 \cdot 5^c < 5^{c+1}.$$

If you still want to use the Myhill-Nerode theorem you can proceed as follows: Pick any two non-negative integers $$i,j$$ with $$i and consider the two words $$x= b^{5^i}$$ and $$x = {5^j}$$. Let $$z = b^{4 \cdot 5^i}$$. Notice that $$xz = b^{5^i + 4 \cdot 5^i} = b^{5^{i+1}} \in L$$ while $$yz = b^{ 5^j + 4\cdot 5^i} \not\in L$$ since $$5^j < 5^j + 4 \cdot 5^i < 5^j + 4 \cdot 5^j = 5^{j+1}$$. Therefore $$z$$ is a distinguishing extension for $$x$$ and $$y$$ and they cannot belong to the same equivalence class for the relation $$R$$ defined by $$\alpha R \beta$$ iff $$\alpha \in \Sigma^*$$ and $$\beta \in \Sigma^*$$ have no distinguishing extension. This shows that the number of equivalence classes in the quotient set $$L_{/R}$$ is not finite and, by the Myhill-Nerode theorem, $$L$$ is not regular.

• what does pumping length mean? Jun 10 '20 at 22:14
• It is just the minimum constant $c$ for which the pumping lemma holds, that is, such that any word $w \in L$ with $|w| \ge c$ can be written as $xyz$, with $|xy| \le c$, $|y| \ge 1$, and $xy^iz \in L$ for all values of $i \ge 0$. See the formal definition on Wikipedia Jun 10 '20 at 22:20
• is there a way to prove this with the myhill-nerode theorem? Jun 10 '20 at 23:21
• See the edited answer. Jun 10 '20 at 23:48
• Pick any natural number $i$. What is the first power of $5$ that is larger than $5^i$? It is $5^{i+1}$. The difference between $5^{i+1}$ and $5^i$ is $5^{i+1} - 5^i = 5^i (5 - 1) = 4 \cdot 5^i$. If you want to append a word $z$ containing the minimum number of $b$s to a string $x \in L$ consisting of $5^i$ $b$s in order to have $xz \in L$, then you will need to select $z = b^{4 \cdot 5^i}$. Jun 11 '20 at 17:16