Graph Theory

Y3S2 Graph Theory Project

Description

A Python program that can build a non-deterministic finite automaton (NFA) from a regular expression, and can use the NFA to check if the regular expression matches a given string of text.

The program uses an algorithm known as Thompson's construction, a method of transforming a regular expression into an equivalent NFA. The code works by composing small NFA fragments that represent part of the regular expression, and then proceeding to build larger NFAs from those smaller NFA fragments. If the given string is accepted by the NFA, the program will output True, and False otherwise.

Operators

The below operators/metacharacters are implemented:

Operator	Represents	NFA Fragment *
.	Concatenation.
|	Alternation/Union.
?	Zero-or-one occurrences of a character.
+	One-or-more occurrences of a character.
*	Zero-or-more occurrences of a character.

* NFA fragment diagrams taken from these slides on Thompson's Construction.

Running

The program can be run as follows, using the -m argument in order to execute the __main__.py module.

$ python3 -m match -r REGEX -t TEXT

Command-Line Arguments

Argument	Description
-h/--help	Prints a help message and then exits.
-v/--version	Shows the program's version number then and exits.
-r/--regex	The regular expression to match.
-t/--text	The string of text you want to try and match against the pattern defined by the regular expression.

Example

Installing with pip

From inside the root of the repository, run:

$ sudo pip3 install .

This will allow you to run the program system-wide, while omitting the python3 -m.

Note: You may first need to apt install python3-pip before installing.

Removing

You can uninstall it again by running sudo pip3 uninstall match.

Testing

Tests are located in the tests/ directory.

Run All Tests

$ python3 -m unittest discover --verbose

Run a Single Test

$ python3 tests/[file_name].py

Documentation

The documentation for this project is deployed on GitHub Pages.

Building the Docs

Note: You may first need to install the Sphinx documentation generator. On Debian-based Linux distributions this can be done by running:

$ sudo apt install python3-sphinx

You should then be able to run make html from within the docs/ directory to reproduce the HTML files, which will be placed in the _build/html directory.

Notes

• The docstrings thoughout this project follow the reStructuredText (reST) format outlined in PEP 287.

• The contents of the docs/ directory were mostly auto-generated using the sphinx-quickstart command, followed by sphinx-apidoc -o . ../match --separate to create the RST files.