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


1 Answer 1


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .