For an alphabet $\Sigma = \{1, +, =\}$ and language

$L= \{ 1^m +1^n =1^{m+n} | m, n ∈ \mathbb{N} \}$, is $L$ regular?

So here are my thoughts: I do not believe this language is regular. This is because I cannot conceive of designing a regular expression, DFA, or NFA for it. There is simply no finite way to keep track of how many $1$'s are in each location relative to $=$ and $+$. However, Myhill-Nerode does not seem to work, as every string in $L$ is a "balanced" equation and adding any number of $1$'s to a string in $L$ would make it no longer a member of $L$. Now, using Myhill-Nerode (and not the Pumping Lemma or any other tools), is there a way to prove that $L$ is regular? Alternatively, if $L$ is actually not regular, I would greatly appreciate any hints as to how to go about designing a regular expression for $L$.


We can prove that $L$ is not regular using the Myhill-Nerode theorem. As in the theorem, define an equivalence relation $\sim$ on $\Sigma^*$ by $x \sim y$ if and only if for all strings $z \in \Sigma^*$, $xz \in L \iff yz \in L$. The theorem then says that $L$ is regular exactly when this equivalence relation has finitely many equivalence classes.

Let $\alpha_n$ be the string $(1^n)$, and $\beta_{i, j}$ be the string $(+ 1^i = 1^j)$. Then when $n \neq m$, we have that $\alpha_n \beta_{m, n+m} \in L$, but $\alpha_m \beta_{m, n+m} \notin L$. Hence, $\alpha_n \not \sim \alpha_m$ whenever $n \neq m$, and so there are infinitely many equivalence classes for $\sim$. So the language is not regular.

| cite | improve this answer | |

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.