This project implements a converter that transforms a Non-deterministic Finite Automaton (NFA) with epsilon transitions into a Deterministic Finite Automaton (DFA). The conversion process is performed using Python, and the results can be tested against a set of input words.
- Reads NFA definitions from a text file.
- Converts the NFA into a DFA while handling epsilon transitions.
- Saves the resulting DFA to an output text file.
- Tests a list of input words against the DFA and records which words are accepted or rejected.
- Outputs the results to a separate text file.
The NFA input file must be formatted as follows:
- States: A single line containing all the states, separated by spaces.
- Initial State: A single line with the initial state.
- Final States: A single line containing all final states, separated by spaces.
- Transitions: Each subsequent line should define a transition in the format:
where:
state symbol next_statestate: Current state.symbol: Input symbol (including 'h' for epsilon transitions).next_state: Next state resulting from the transition.
The DFA output file will be formatted as follows:
- States: A single line containing all DFA states, separated by spaces.
- Initial State: A single line with the DFA's initial state.
- Final States: A single line containing all final states of the DFA, separated by spaces.
- Transitions: Each subsequent line defines a transition in the format:
state symbol next_state
The word list input file should contain each word on a new line. These words will be tested against the DFA.
The results output file will contain the acceptance results for each word, formatted as:
word accepted
word **rejected**
- Place the required input files (
nfa.txtandwords.txt) in the project directory. - Run the
mainfunction in the script.python your_script.py
- After execution, check the
output.txtandresults.txtfiles for the DFA definition and word testing results, respectively.