Featured Articles

Trusted Boot (Anti-Evil-Maid, Heads, and PureBoot)
Hardening Guide for phpList
Continuous Documentation: Hosting Read the Docs on GitHub Pages (2/2)
WordPress Multisite on the Darknet (Mercator .onion alias)
Nightmare on Lemmy Street (A Fediverse GDPR Horror Story)
Crowdfunding on Crowd Supply (Review of my experience)
Detecting (Malicious) Unicode in GitHub PRs
WordPress Profiling with XHProf (Debugging & Optimizing Speed)
Introducing BusKill: A Kill Cord for your Laptop
previous arrow
next arrow

RegEx 2 DFA in Python

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