Chapter 4 : Properties of Regular Languages - Equivalent states

Chapter 4 : Properties of Regular Languages - Equivalent states

by ALVISE GARBERINO -
Number of replies: 4

Good evening, I am rereading Chapter 4 on the properties of regular languages and I came across the example concerning Equivalent states:

Let A = (Q,Σ,δ,q0,F) be a DFA, and let p,q ∈ Q.
We define p ≡ q ⇔ ∀ w ∈ Σ* : δ^(p,w) ∈ F if and only if δ^(q,w) ∈ F

Where I assume w refers to a string (following the corollary presented in Chapter 1, page 39 of the first set of slides).

In the example shown below, I do not understand why we are saying that A ≡ E, given that for the string "0" this statement is not satisfied.image.png
image%20%281%29.png

In reply to ALVISE GARBERINO

Re: Chapter 4 : Properties of Regular Languages - Equivalent states

by NICOLA RANZOLIN -
Hi Alvise,

The fact that δ(A,0) = B and δ(E,0) = H does not contradict the equivalence between A and E. Equivalence does not require the immediate successors to be the same; it requires that for every string w ∈ ∑* = {0,1}*, the automaton reaches a final state from A on w if and only if it reaches a final state from E on w (the definition you quoted).

In this DFA, reading 0 from A leads to B and reading 0 from E leads to H, but both B and H are non-accepting (good!), and for every possible continuation x, the states reached from B and from H behave identically with respect to acceptance (good!). The same holds for input 1, where both transitions lead to non-accepting states that again match in their future behaviour.

For this reason, A and E produce the same acceptance outcome for all strings in ∑*, and are therefore equivalent, even though their immediate successors differ.

Hope it helps.
In reply to ALVISE GARBERINO

Re: Chapter 4 : Properties of Regular Languages - Equivalent states

by Giorgio Satta -

Dear Alvise, in the definition of equivalence of two states of a FSA, \( w \) is a string since the statement specifies \( w \in \Sigma^\ast\), where \( \Sigma^\ast \) is the set of all strings over \( \Sigma \) of length zero or more.

As for the statement \( A \equiv E \), I do not see a contradiction. Note that the definition of equivalence does not require that \( B \) and \( H \) must be the same state, it only requires that these two states must both be in \( F \), the set of final states of the automaton, or else must both be outside of \( F \), and \( B \) and \( H \) satisfy the second case.

Please let me know if I have answered to your question.

In reply to Giorgio Satta

Re: Chapter 4 : Properties of Regular Languages - Equivalent states

by ALVISE GARBERINO -

So if I understood correctly, the key ideas are:

  • If δ^(p,w) reaches an accepting state (i.e., ∈ F), then δ^(q,w) must also reach an accepting state (∈ F).

  • And if δ^(p,w) reaches a non-accepting state (i.e., ∉ F), then δ^(q,w) must also reach a non-accepting state (∉ F).

So for every given string w, the output (accepted or rejected) must be the same. In other words, p and q do not necessarily have to reach the same state, but the state(s) they reach must yield the same output.