COSC5315 PROGRAM-3 Fall 2020

DFSA Equivalence Checker

(Last updated on August 20, 2019)

TASK:

Write a well-structured program for checking equivalence of DFSA’s.

This will take the following steps:

1. Eliminate unreachable state(s)

As state#1 is the initial state, any state unreachable from state#1

must be identified and removed from further consideration (before taking

the next step of minimization)

2. Make sure that the DFSA is completely specified.

3. Minimize each DFSA.

This step will check if two accepting states or two non-accepting states

are equivalent as equivalent states can be combined into just one state.

Two states are equivalent if there is no “Distinguishing” string for them.

4. Compare two minimized DFSA’s for their equivalence.

Two Minimized DFSA’s are equivalent if and only if

a. they have the same total number of states and

b. they have the same number of accepting states and

c. they have the asme number of non-accepting states and

b. they have the same set of transitions after a suitable renumbering of

states (like a lexigraphical ordering)

Output Requirements:

1. For each input DFSA,

a. the input set of transitions with an indicator of accepting state(s)

b. the set of transitions (lexigraphically ordered) for the minimized DFSA

along with an indicator of accepting state(s)

2. All pairs of equivalent DFSA’s

INPUTS TO BE USED:

Use the following four DFSA’s.

Note that each transition of a DFSA is represented by a triple of the form:

(originating-state, input-symbol, terminating-state)

DFSA-1: #4 is accepting