# Prove that $\{1^m+1^n = 1^{m+n}\}$ is not regular using Myhill–Nerode

Consider the alphabet $Σ = \{1, +, =\}$ and the following language, $PLUS = \{ 1^m + 1^n = 1^{m+n} \mid m, n ∈ ℕ \}$. Prove with Myhill-Nerode that PLUS is not a regular language.

I know how I should use Myhill-Nerode here and how I should show that any two strings in the infinite set $S$ are distinguishable, but I am stuck at defining my infinite set S for this language. I tried $S = \{1^n \mid \text{$n$is a natural number} \}$ but I don't think it works.

If $n \neq m$ then $1^m+1=1^{m+1} \in PLUS$ but $1^n+1=1^{m+1} \notin PLUS$.
• I'll let you figure that out. Don't forget that $1^n$ is shortcut for $n$ copies of $1$. – Yuval Filmus Dec 1 '17 at 16:39
• That's the idea, though I'm not sure why you are considering $1^m+1$ and $1^n+1$. – Yuval Filmus Dec 1 '17 at 17:00