Distinguishing Suffixes

 
Figure 1: An NFA for L = .

• 00 and 000 must be distinguished because and .
  
• 00 and 0000 need not be distinguished because both 00z and 0000z either are in L or not in L, for all suffixes z.

Def. Given x and y, if there exists z, such that

or

then z distinguishes x & y.

Then, .

Otherwise, if distinguishing suffix, then
can be same as

e.g.

 
Figure 2: An NFA for L = .

1. 00 and 01 are distinguished by .
2. 01 and 001 are not distinguishable.
3. 0 and 00 are distinguished by 0.