For my Discrete Mathematics II course at UCF (COT4210), I had to do some implementation with Finite State Machines. My favorite of our tasks (though the most difficult) was to convert a Regular Expression (RE) to an equivalent Deterministic Finite Automata (DFA). And since our professor let us use any language, I tried to branch out from Java & C (which are annoyingly overused in Academia). I decided to teach myself Python. And it turns out, it was a good choice too–considering it’s wonderful built-in functionality for Lists, and the heart of this program is a huge 2D array defining the automata’s transition function. Also, I miss scripting languages–especially when I’m writing a program as a learning experiment as opposed to trying to make it as efficient as possible.
So, without further Ado: here’s my code. It reads a RE in postfix notation from input.txt. Two cautions about postfix REs:
You must explicitly state concatenation The Kleen Star is already a postfix operator in REs, so it doesn’t really work to use a mathematical infix2postfix library, as it treats the kleen star like an infix multiplicative operator. I treat it as an operand and throw it directly into the
. . . → Read More: RegEx 2 DFA in Python
