Using Myhill-Nerode to prove a language is not regular?

[Lolligirl]

Hello everyone! :D

I've been looking at the definition and proof of the Myhill-Nerode theorem for awhile now and cannot figure out what the notation is trying to tell me. Here are the languages I'm trying to apply it to, and then I'll explain what I think we're trying to do:

Question:
Prove these two languages are not regular by using Myhill-Nerode:
1. { a^Fib(k) | k>0 } (this is set {a¹, a¹, a², a³, a⁵, a⁸, a¹³, a²¹, … })

2. { w | w ∈ {a, b}* and w = w^R } (this is the set of palindromes; it contains strings like aa, abba, abaaba, etc.)

Okay, so I know Myhill-Nerode basically gives us a property P such that R is regular if and only if P(R). And I know an equivalence relation is reflexive, symmetric, and transitive and that we want to divide these languages up into right invariant equivalence classes. But how do we pick the classes we're considering (if that makes sense)? What are we looking for each time we're trying to apply this theorem?

For the Fibonacci one, for instance, would we choose to look at a^Fib(j) for j >= 0?
And for the palindrome one, ww^{R^j} for j >= 0?

I'm not sure what we're trying to look for here. Could anyone help me figure this out?

 

[Evgeny.Makarov]

But how do we pick the classes we're considering (if that makes sense)? What are we looking for each time we're trying to apply this theorem?

The theorem says that a language $L$ is regular iff the number of equivalence classes in the associated relation $\equiv_L$ is finite. Here $u\equiv_L v$ if $uw\in L\iff vw\in L$ for all $w$. So to prove that $L$ is not regular it is sufficient to find infinitely many words that are not equivalent w.r.t. $\equiv_L$.

For Fobinacci numbers, prove that $a^{\text{Fib}(k)}$ where $\text{Fib}(k)>1$ are not equivalent. Note that the equivalence relation is defined on all words, not only on those in the language, and often it is convenient to choose an infinite set of non-equivalent words not necessarily in the language. But in this case the words in the language form such set as well.

For $L=\{ww^R\mid w\in\{a,b\}^*\}$, show that $a^mb\not\equiv_L a^nb$ if $m\ne n$.

 

[Lolligirl]

I'm sorry, but what does $\equiv_L$, and subsequently $u\equiv_L v$ if $uw\in L\iff vw\in L$ for all $w$, mean? I always get a little hung up on the notation. :B Is $\equiv_L$ "the equivalence class of L", or?

 

[Evgeny.Makarov]

The notation $\equiv$ is commonly used to denote equivalence relations. The equivalence class of $x$ w.r.t. $\equiv$ is often denoted by $[x]_{\equiv}$ or just $[x]$.

One way to state the Myhill-Nerode theorem is to introduce a concrete equivalence relation based on the language $L$ itself. I denoted it by $\equiv_L$. By definition, $u\equiv_L v$ if $uw\in L\iff vw\in L$ for all $w$. Then the theorem says that $L$ is regular iff $\equiv_L$ has a finite number of equivalence classes.

Perhaps in your course the theorem was formulated in a slightly different way. Could you post it? The idea of proving that $L$ is not regular is still the same: to find infinitely many words that can be distinguished (w.r.t. membership in $L$) by their suffixes. That is, to find $u_1,u_2,\dots$ such that if $i\ne j$, then there exists a $w$ such that $u_iw\in L$, but $u_jw\notin L$ or vice versa.

 

[Lolligirl]

The version I've seen is this:

Myhill-Nerode Theorem
The following are equivalent:
1. L is accepted by some DFA.
2. L is the union of some of the classes of a right invariant equivalence relation, R, of finite index.
3. The specific right invariance equivalence relation R_L where x R_L y iff ∀z [ xz ∈ L iff yz ∈ L ] has finite index.

Definition: R is a right invariant equivalence relation iff R is an equivalence relation and ∀z [ x R y implies xz R yz ].
Note: This is only meaningful for relations over strings.

I see how this is pretty similar to the one you posted! For the palindrome one, you are saying that we must prove a^mb is not in the same equivalence class of L as aⁿb if m is not equal to n? So on the Fibonacci problem, what else do we need to do in regards to the equivalence classes?

Here's my try on the Fibonacci one:
Consider aⁱ and a^j where i,j > 0 but i != j.
aⁱa^i-1 is in the language, but a^ja^j-1 is not when i != j.
This shows that there is a separate equivalence class [a^ja^j-1] induced by R_L for each i != j.
Thus, the index of R_L is infinite and thus L cannot be regular.

 

[Evgeny.Makarov]

The version I've seen is this:

Myhill-Nerode Theorem
The following are equivalent:
1. L is accepted by some DFA.
2. L is the union of some of the classes of a right invariant equivalence relation, R, of finite index.
3. The specific right invariance equivalence relation R_L where x R_L y iff ∀z [ xz ∈ L iff yz ∈ L ] has finite index.

My version states the equivalence of (1) and (3).

And for the palindrome one, you are saying that we must prove a^mb is not in the same equivalence class of L as aⁿb if m is not equal to n?

Yes.

Here's my try on the Fibonacci one:
Consider aⁱ and a^j where i,j > 0 but i != j.
aⁱa^i-1 is in the language, but a^ja^j-1 is not when i != j.

Do you mean $a^{\text{Fib}(i-1)}$ instead of $a^{i-1}$ and similarly for others? First, both $a^{\text{Fib}(i)}a^{\text{Fib}(i-1)}\in L$ and $a^{\text{Fib}(j)}a^{\text{Fib}(j-1)}\in L$. Second, adding different suffixes does not disprove $R_L$. What you probably mean is that $a^{\text{Fib}(i)}a^{\text{Fib}(i-1)}\in L$, but $a^{\text{Fib}(j)}a^{\text{Fib}(i-1)}\notin L$ if $\text{Fib}(i),\text{Fib}(j)>1$.

 

[Lolligirl]

Okay, I think I'm getting the palindrome one now after looking over the explanation over and over.

So, with the palindrome question, let's use the pairs aba and bab, which both belong to L, and add ba to them both. Then we get ababa, which still belongs to L, but babba, which does not. Thus, L cannot be regular. Is that correct?

For the Fibonacci one, though, I don't think my original thought of a^Fib(i) and a^Fib(j), and adding a^Fib(i-1) to them both, would work. I say that because, let's say we choose i to be 5 and j to be 3. Then neither a^Fib(i)a^Fib(i-1) or a^Fib(j)a^Fib(i-1) belong to L because a^Fib(i-1) aka a^Fib(4) doesn't. And then if I choose two numbers i and j lower than that, they both end up belonging to L. Is my chosen suffix to add, wrong?

 

[Evgeny.Makarov]

So, with the palindrome question, let's use the pairs aba and bab, which both belong to L, and add ba to them both. Then we get ababa, which still belongs to L, but babba, which does not. Thus, L cannot be regular. Is that correct?

It is true that $aba\in L$, $bab\in L$, $ababa\in L$ and $babba\notin L$, but it does not show that $L$ is not regular because

to prove that $L$ is not regular it is sufficient to find infinitely many words that are not equivalent w.r.t. $\equiv_L$.

Note also that you don't have to choose the first pair of words in $L$ (though this is not wrong, either). As I said earlier,

Note that the equivalence relation is defined on all words, not only on those in the language, and often it is convenient to choose an infinite set of non-equivalent words not necessarily in the language.

For the Fibonacci one, though, I don't think my original thought of a^Fib(i) and a^Fib(j), and adding a^Fib(i-1) to them both, would work. I say that because, let's say we choose i to be 5 and j to be 3. Then neither a^Fib(i)a^Fib(i-1) or a^Fib(j)a^Fib(i-1) belong to L because a^Fib(i-1) aka a^Fib(4) doesn't.

I don't agree. a^Fib(i)a^Fib(i-1) = a^{Fib(i)+Fib(i-1)} = a^Fib(i+1) ∈ L. I also don't know why you say that a^Fib(4) ∉ L since $\{L=a^{\text{Fib}(k)}\mid k>0\}$.

 

[Lolligirl]

I am not sure I understand what you mean...pick an infinite set? So you mean pick a form that isn't specific? So instead of aba and bab and adding ba to them, something like choosing aⁱbⁱaⁱ and bⁱaⁱbⁱ, then adding ba to those instead?. I thought we were just trying to disprove regularity for just one case and thus disproved it, that must've been where I misunderstood.

So then I'm more confused on the Fibonacci one. What does a^Fib(i) actually represent? That there is Fib(i) number of a's in the string? But what is Fib(i)? Would Fib(4) be the fourth Fibonacci number, and thus be 3?

 

[Evgeny.Makarov]

I am not sure I understand what you mean...pick an infinite set?

Yes.

So instead of aba and bab and adding ba to them, something like choosing aⁱbⁱaⁱ and bⁱaⁱbⁱ, then adding ba to those instead?.

Yes, something like that. I suggested a suitable infinite family of words back in post #2.

I thought we were just trying to disprove regularity for just one case

We are. It's just a question of facts we rely on to disprove regularity. In this case, it's Myhill-Nerode theorem, which says that $L$ is regular iff the number of equivalence classes of $R_L$ (which I denoted by $\equiv_L$) is finite. So, disproving the fact that $L$ is regular using this theorem consists of showing that the number of equivalence classes of $R_L$ is infinite. And this is shown by exhibiting infinitely many words such that no two of them are related by $R_L$.

So then I'm more confused on the Fibonacci one. What does a^Fib(i) actually represent? That there is Fib(i) number of a's in the string?

Yes.

But what is Fib(i)? Would Fib(4) be the fourth Fibonacci number, and thus be 3?

That's how I understood it. The only thing is that there are slightly different definitions of Fibonacci numbers: some start with 1, 1 and others with 0, 1. In any case, as I understand it, Fib(i) is a Fibonacci number by definition.