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

1. Remove degenerate rules
2. Removing terminal sequences
3. Fix empty rules
4. Collapse similar starting rules
5. Construct the canonical regular grammar (DFA)
6. Display canonical grammar
7. A canonical regular grammar from a regular expression.
8. Minimization of the Regular Grammar
9. Artifacts

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

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.