equivalence of states in DFAs

• EQUIVALENCE OF STATES IN DFAs

  • Two states p and q are equivalent if, for all strings w, ∂*(p,w) is a final state if and only if ∂*(q,w) is a final state as well.

  -> Thus, p and q cannot be distinguished solely based on the acceptance or rejection of any string.

  • If two states are not equivalent, they are distinguishable states: There is at least one string w for which ∂*(p,w) and ∂*(q,w) lead to different acceptance outcomes
• EXAMPLE

  • Consider states A and G. String does not distinguish them, because they are both non-accepting states.
  • However, 01 distinguishes A from G, because ∂*(A,01) = C, ∂*(G,01) = E, C is accepting, and E is not.

  
• TABLE FELLING ALGORITHM

  Theorems:

  • If two states are not distinguished by the table- lling algorithm, then the states are equivalent.
  • The equivalence of states is transitive.

  
• EXAMPLE

  
• EXAMPLE (cont.)

  
• EXAMPLE (cont.)