0
$\begingroup$

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.

Improve this question
$\endgroup$
2
$\begingroup$

If $n \neq m$ then $1^m+1=1^{m+1} \in PLUS$ but $1^n+1=1^{m+1} \notin PLUS$.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thanks for the answer but how come 1^m + 1 = 1^{m+1} ∈ PLUS ? since 1^{m+1} is not equal to 1^{m+n} as required by the language? $\endgroup$ – user75706 Dec 1 '17 at 16:27
  • $\begingroup$ I'll let you figure that out. Don't forget that $1^n$ is shortcut for $n$ copies of $1$. $\endgroup$ – Yuval Filmus Dec 1 '17 at 16:39
  • $\begingroup$ Thank you for the lead @YuvalFilmus. Do you think the following proof is correct: Consider the alphabet Σ = {1, +, = } and the language PLUS as defined above. We will show that PLUS is not regular. Let S = {1^m | m ∈ N}. This set is infinite. We claim that any two distinct strings in S are distinguishable relative to PLUS. Consider any two strings 1^m, 1^n ∈ S. Consider the strings 1^m + 1 and 1^n + 1. We see that 1^m + 1 = 1^{m+1} ∈ PLUS and 1^n + 1 = 1^{m+1} not in PLUS. Therefore, 1^m and 1^n are distinguishable relative to PLUS. Thus, by the Myhill-Nerode theorem, PLUS is not regular. $\endgroup$ – user75706 Dec 1 '17 at 16:57
  • $\begingroup$ That's the idea, though I'm not sure why you are considering $1^m+1$ and $1^n+1$. $\endgroup$ – Yuval Filmus Dec 1 '17 at 17:00
  • $\begingroup$ I thought I need to explain why one string is in the language and the other is not after I append the same "w" at the end of each. In this case the "w" is the string "1". $\endgroup$ – user75706 Dec 1 '17 at 17:02

Your Answer

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