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.


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<j$ 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.

  • $\begingroup$ what does pumping length mean? $\endgroup$
    – WindBreeze
    Jun 10 '20 at 22:14
  • $\begingroup$ 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 $\endgroup$
    – Steven
    Jun 10 '20 at 22:20
  • $\begingroup$ is there a way to prove this with the myhill-nerode theorem? $\endgroup$
    – WindBreeze
    Jun 10 '20 at 23:21
  • $\begingroup$ See the edited answer. $\endgroup$
    – Steven
    Jun 10 '20 at 23:48
  • 1
    $\begingroup$ 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}$. $\endgroup$
    – Steven
    Jun 11 '20 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.