Regular Grammars - The Beard Sage

A Context-Free Grammar (CFG) is a regular grammar if every rule is of the form

$\begin{align*} A &\rightarrow aB \\ A &\rightarrow B \\ A &\rightarrow a \\ A &\rightarrow \epsilon \\ \end{align*}$

where $A, B \in V$ and $a \in \Sigma$ .

NFA to Regular Grammar

Consider the following NFA

Rendered by QuickLaTeX.com

The name of the states become the variables of the regular grammar. Each transition on an input symbol gets converted to a rule as shown below.

$\begin{align*} A &\rightarrow \epsilon B \\ A &\rightarrow \epsilon D \\ B &\rightarrow 1B \\ B &\rightarrow 0C \\ C &\rightarrow 0B \\ C &\rightarrow 1C \\ D &\rightarrow 0D \\ D &\rightarrow 1E \\ E &\rightarrow 0E \\ E &\rightarrow 1E \\ \end{align*}$

The final states will have the following additional rules

$\begin{align*} C &\rightarrow \epsilon \\ E &\rightarrow \epsilon \\ \end{align*}$

The start state of the NFA will be the start variable of the regular grammar ( $A$ ). Here is the final grammar in condensed form

$\begin{align*} A &\rightarrow \epsilon B | \epsilon D \\ B &\rightarrow 1B | 0C \\ C &\rightarrow 0B | 1C | \epsilon \\ D &\rightarrow 0D | 1E \\ E &\rightarrow 0E | 1E | \epsilon \\ \end{align*}$

Regular Grammar to NFA

Consider the following regular grammar

$\begin{align*} S &\rightarrow 0S | 0T | 0 \\ T &\rightarrow 1T | 0T | 0A | 1 \\ A &\rightarrow 0 | \epsilon \\ \end{align*}$

To account for the $A \rightarrow a$ rules, a new variable can be added as shown below

$\begin{align*} S &\rightarrow 0S | 0T | 0Z \\ T &\rightarrow 1T | 0T | 0A | 1Z \\ A &\rightarrow 0 | \epsilon \\ Z &\rightarrow \epsilon \\ \end{align*}$

Each rule defines the transition between states on that symbol. The variables that go to $\epsilon$ are marked as final. Here is an equivalent NFA.

Rendered by QuickLaTeX.com

NFA to Regular Grammar

Regular Grammar to NFA

Leave a Reply Cancel reply