doubt toc

Question

the set L ⊆Σ*  is accepted by some FA if and only if L is the union of some of the equivalence classes of a right invariant equivalence relation of finite index........................what is its meaning and is true or false??

Comments

Myhill-Nerode Theorem

 

---

can u explain i know this is definition but i am not understanding

---

@eyeamgj

This is what it says in simple words.

Myhill-Nerode Theorem : If the definition of the language L divides all strings into finite number of classes then L is a regular language. OR(same) For a language L defined over an alphabet Σ, L partitions Σ^* into distinct classes. If L generates finite number of classes, then L is regular.

This theorem helps in deciding whether the language is regular or not. 

---

Example:

Strings ending in b; Σ = {a, b}

L partitions Σ* into following classes:

c₁ : Set of all stings ending in a

c₂ : Set of all stings ending in b

Since these are finite classes, the language is regular.

---

Hope it helps?

Answer 1

This is true as it is nothing but the definition of My Hill Nerode Theorem.

Few definitions are below for your reference.

Definition 1. Let Σ be an alphabet and ~ a relation of equivalency on Σ*. Then relation ~ is right invariant if for all u, v, w ∈ Σ*:

u ~ v <=> uw ~ vw

Definition 2. Let L be a language (not neccessarily regular) over Σ. We define relation ~Lcalled prefix equivalence on Σ* as follows:

u ~L v <=> ∀w ∈ Σ*: uw ∈ L <=> vw ∈ L

You can further read it here  http://radek.io/2011/10/24/myhill-nerode-theorem-in-practice/