Computation Toolkit - practical assignment
P1. NFA to DFA Converter
A Python implementation of the subset construction algorithm to convert a Non-Deterministic Finite Automaton (NFA) with ε-transitions to an equivalent Deterministic Finite Automaton (DFA).
Algorithm
- Computes ε-closures for NFA states.
- Generates DFA states, transitions, and accept states.
- Handles ε-transitions during DFA state construction.
Usage
Input Format
Define your NFA as follows:
nfa_states
: Set of NFA states (e.g., {'q0', 'q1', 'q2'}
).
nfa_alphabet
: List of symbols including 'ε'
(e.g., ['a', 'b', 'ε']
).
nfa_transitions
: Dictionary where keys are tuples (state, symbol)
, and values are sets of next states. (e.g., { ('q0', 'ε'): {'q1'}, ('q1', 'a'): {'q1', 'q2'}, ('q1', 'b'): {'q1'}, ('q2', 'a'): {'q2'}, }
).
nfa_start
: The start state (e.g., 'q0'
).
nfa_accept
: Set of accept states (e.g., {'q2'}
).
Function Call
from computation_toolkit import nfa_to_dfa
dfa_states, dfa_alphabet, dfa_transitions, dfa_start, dfa_accept = nfa_to_dfa(
nfa_states, nfa_alphabet, nfa_transitions, nfa_start, nfa_accept
)
P2. Check CFG Ambiguity given a string
A program to determine if a given string has more than one parse tree under a provided context-free grammar (CFG), indicating ambiguity for that string. Uses an shift-reduce bottom up parser to handle common sources of ambiguity.
Algorithm
- Detects ambiguity by checking for multiple valid parse trees.
- Uses BFS-based shift-reduce parsing to build the parse trees.
Usage
Specify your CFG as a dictionary where:
- Keys are non-terminals (e.g.,
"E"
).
- Values are lists of productions (e.g.,
[["E", "+", "E"], ["a"]]
).
Example (ambiguous arithmetic grammar):
from computation_toolkit import has_multiple_parses
grammar = {
"E": [["E", "+", "E"], ["E", "*", "E"], ["a"]]
}
start_symbol = "E"
input_string = "a+a*a"
print(has_multiple_parses(grammar, start_symbol, input_string))
P3. Turing Machine to add two uniary numbers
A Python implementation of a Turing Machine that computes the sum of two unary numbers separated by a +
symbol.
Algotithm
- Implements a 3-state Turing Machine (Start, MoveToEnd, EraseLast)
- Handles edge cases (empty numbers, missing separator)
- Includes error checking for invalid inputs
- Unit test coverage for all major cases
Usage
from computation_toolkit import tm_add
input_str = "111+11"
print(tm_add(input_str))
Running the Tests
To run the tests, use the following command:
python -m unittest discover tests -v
Author