Are addition expressions a regular language?

2018-03-09 04:19:06

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

$L= \{ 1^m


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