Can `DONT_CARE` match with `EPSILON`?

[koniksedy]

We need to revise the nft::product function. Currently, it allows matching the DONT_CARE symbol with EPSILON and produces EPSILON as the result of this match. This does not feel right, because DONT_CARE should mean "an arbitrary alphabet symbol," with epsilon excluded. However, the existing general implementation of nft::compose somehow relies on this behavior. We need to figure out why, and whether it can be done in a cleaner way.

[jurajsic]

Are DONT_CARE symbols used anywhere? Are they planned to be used for something? Because I am starting to wonder if it would not be better to just completely remove the support for them....

[Adda0]

They are supposed to be used for NFAs with BDDs on the transitions where DONT_CARE symbols are commonly used.

[koniksedy]

Actually, DONT_CARE symbols are used inside the general algorithm for transducer composition. They are used on the waiting loops, which handle cases where one transducer needs to wait because the other transducer has an EPSILON on the synchronization level that it cannot synchronize with. In such cases, the transducer waits in the waiting loop to handle the mismatch with EPSILON symbols on its own tracks/levels and a DONT_CARE symbol on the tracks/levels of the other transducer.

[koniksedy]

It feels to me like rubber duck debugging. So, I think you would want the DONT_CARE symbol to match the EPSILON symbol. This is because DONT_CARE is used in the waiting loops as a copy mechanism that copies everything from the other transducer into the resulting product transducer. And since you may want to have an EPSILON on one of the transitions, you would also want
the EPSILON to be copied in this way.