# Converting a Regular Expression to DFA using Regular Grammar

A regular grammar can in theory have rules with any of the following forms

- \[A \rightarrow a\]
- \[A \rightarrow a B\]
- \[A \rightarrow a b c B\]
- \[A \rightarrow B\]
- \[A \rightarrow \epsilon\]

with no further restrictions. This is the direct equivalent grammar for
a nondeterministic finite state automaton (**NFA**).
However, for working with regular grammars,
such freedom can be unwieldy. Hence, without loss of generality, we define
a canonical format for regular grammars, to which any regular grammar can
be converted to.

- \[A \rightarrow a B\]
- \[S \rightarrow E\]
- \[E \rightarrow \epsilon\]

where given a nonterminal \(A\) and a terminal symbol \(a\) at most one of
its rules will start with a terminal symbol \(a\). That is, if the original
grammar had multiple rules that started with \(a\), they will be collected
into a new nonterminal symbol. Further, there will be at most one terminal
symbol in a rule. That is, if there are more terminal symbols, then we bundle
that to a new nonterminal symbol.
Finally, the \(\epsilon\) is attached to the \(E\) symbol, which is the
only termination point. If the language contains \(\epsilon\), then the
single degenerate rule, \(S \rightarrow E\) is added to the rules.
As you can see, each node has at most one
transition for a given terminal symbol. Hence, this canonical form is
equivalent to a deterministic finite state automation (**DFA**).

What is the use of such a DFA compared to NFA? the great thing about a DFA is that there is exactly one state to which a DFA can transition to for any given alphabet from any given state. This means that when parsing with a regular grammar that directly represents a DFA, there is never a reason to backtrack! This means that when we parse with the grammar from such a DFA using an LL(1) parser, we are guaranteed \(O(n)\) matching time.

We start with importing the prerequisites

## Contents

- Remove degenerate rules
- Removing terminal sequences
- Fix empty rules
- Collapse similar starting rules
- Construct the canonical regular grammar (DFA)
- Display canonical grammar
- A canonical regular grammar from a regular expression.
- Minimization of the Regular Grammar
- Artifacts

**Important:** Pyodide takes time to initialize.
Initialization completion is indicated by a red border around *Run all* button.

## System Imports

These are available from Pyodide, but you may wish to make sure that they are installed if you are attempting to run the program directly on the machine.- sympy

## Available Packages

These are packages that refer either to my previous posts or to pure python packages that I have compiled, and is available in the below locations. As before, install them if you need to run the program directly on the machine. To install, simply download the wheel file (`pkg.whl`) and install using `pip install pkg.whl`.- simplefuzzer-0.0.1-py2.py3-none-any.whl from "The simplest grammar fuzzer in the world".
- gatleastsinglefault-0.0.1-py2.py3-none-any.whl from "Specializing Context-Free Grammars for Inducing Faults".
- earleyparser-0.0.1-py2.py3-none-any.whl from "Earley Parser".
- hdd-0.0.1-py2.py3-none-any.whl from "Hierarchical Delta Debugging".
- ddset-0.0.1-py2.py3-none-any.whl from "Simple DDSet".
- rxfuzzer-0.0.1-py2.py3-none-any.whl from "iFuzzing With Regular Expressions".
- rxregular-0.0.1-py2.py3-none-any.whl from "Regular Expression to Regular Grammar".

The imported modules

We start with a few common rules. First, we define the empty rule.

```
<_> :=
```

We also define our `TERMINAL_SYMBOLS`

Then, use it to define `NT_ANY_STAR`

```
<.*> := . <.*>
| <NT_EMPTY>
```

Use it to also define `NT_ANY_PLUS`

```
<.+> := . <.+>
| . <NT_EMPTY>
```

use any_plus where possible.

## Remove degenerate rules

A degenerate rule is a rule with a format \(A \rightarrow B\) where \(A\) and \(B\) are nonterminals in the grammar. The way to eliminate such nonterminals is to recursively merge the rules of \(B\) to the rules of \(A\).

Using it

## Removing terminal sequences

A terminal sequence is a sequence of terminal symbols in a rule. For example, in the rule

```
<A> ::= a b c <B>
```

`a b c`

is a terminal sequence.
We want to replace such sequences by a new nonterminal. For example,

```
<A> ::= a <Aa>
<Aa> ::= b <Aab>
<Aab> ::= c <B>
```

Using it

## Fix empty rules

If there are any rules of the form \(A \rightarrow b\), we replace it by \(A \rightarrow b E\), \(E \rightarrow \epsilon\). Next, if we have rules of the form \(A \rightarrow \epsilon\), and \(B \rightarrow a A\) then, we remove the \(A \rightarrow \epsilon\) and add a new rule \(B \rightarrow a E\) The reason for doing this is to make sure that we have a single termination point. If you are using NT_ANY_STAR, then make sure you run this after (or use NT_ANY_PLUS instead).

## Collapse similar starting rules

Here, the idea is to join any set of rules of the form \(A \rightarrow b B\), \(A \rightarrow b C\) to \(A \rightarrow b \,or(B,C)\). We use the powerset construction from Automata theory for accomplishing this.

First, we define the epsilon closure. Epsilon closure of a nonterminal is any nonterminal that is reachable from a given nonterminal symbol without consuming any input.

Using it

We can also provide a name for such closures.

Using it

Next, we identify the acceptance states.

Using it

## Construct the canonical regular grammar (DFA)

The procedure is as follows: Start with the start symbol. While there are unprocessed nonterminals, remove one unprocessed nonterminal, then for each terminal symbol that starts its rules,

Using it

Another example

## Display canonical grammar

We also need the ability to compactly display a canonical regular grammar and we define it as below.

Make sure it works

## A canonical regular grammar from a regular expression.

This function extracts the DFA equivalent grammar for the regular expression given.

Using it.

## Minimization of the Regular Grammar

At this point, we have a DFA that is represented as a grammar, where the states in the DFA are nonterminal symbols in the grammar and terminals are the transitions. However, this DFA is not necessarily minimal. Interestingly, Brzozowski observed that if you reverse the arrows in the DFA, resulting in an NFA, and then convert the NFA to DFA, then do this again, the resulting DFA is minimal. However, this can have exponential worst case complexity. Hence, we look at a more common algorithm for minimization. The Hopcroft algorithm (1971) is based on partition refinement. We start with a matrix nonterminals, and iteratively refine them.

Using it.

At this point, all that remains to be done is to merge the nonterminals in the
pairs which are indistinguished. That is, the value is `None`

.

Using it.

The runnable code for this post is available here.

## Artifacts

The runnable Python source for this notebook is available here.

The installable python wheel `rxcanonical`

is available here.