up vote 0 down vote favorite
2

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.

share|cite|improve this question
up vote 2 down vote

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

share|cite|improve this answer
  • 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? – user75706 Dec 1 '17 at 16:27
  • 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
  • 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. – user75706 Dec 1 '17 at 16:57
  • 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
  • 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". – user75706 Dec 1 '17 at 17:02

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.