Regular Grammars¶

1. Regular Grammars¶

Regular grammars are another way to describe regular languages. Recall that a grammar is made of of terminals, variables, and production rule. As the name implies, a regular grammar is a special type of grammar (we will see plenty of grammars later that are not regular). Which begs the question: What makes a grammar regular? Before we can properly answer that, we need some definitions.

Suppose we have the following Grammar $G = (V, T, S, P)$ where,

$\begin{split}\begin{array}{lll} & & \mbox{represented by} \\ V & \mbox{variables (nonterminals)} & A,B,..,Z (that is, capital letters)\\ T & \mbox{terminals} & a,b,..,z,0,1,...9 (lower case letters and numbers)\\ S & \mbox{start symbol} \\ P & \mbox{productions (rules)}\\ \end{array}\end{split}$

$V$ , $T$ , and $P$ are finite sets.

Linear grammar: A grammar is linear if has a single variable in the RHS of every production rule.

$\begin{split}\begin{array}{c} \mbox{All productions are of the form} \\ A \rightarrow xB \\ A \rightarrow Cx \\ A \rightarrow x \\ \mbox{where}\ A,B,C \in V, x \in T^* \end{array}\end{split}$

In this grammar, each production rule has at most one variable on the RHS. (Note: It does not need to be the same terminal $x$ in every production!)

Right-linear grammar: This is a special case of linear grammar. If a grammar is linear and any variable, if it exists, always occurs at the right end of the RHS, then the grammar is called a Right-linear grammar. For example, the grammar:

$\begin{split}\begin{array}{c} A \rightarrow xB \\ A \rightarrow xC \\ A \rightarrow y \\ \mbox{where}\ A,B,C \in V, x,y \in T^* \end{array}\end{split}$

Note: $x$ or $y$ is a string of length 0 or more. Each production has at most one variable, so the grammar is linear. The variables (B and C) are at the end of the RHS, so it is a right linear grammar.

Left-linear grammar: This is the same as Right-linear grammar, but the occurance of any variable, if it exists, is at the begining of each production RHS. For example,

$\begin{split}\begin{array}{c} A \rightarrow Bx \\ A \rightarrow Cy \\ A \rightarrow x \\ \mbox{where}\ A,B,C \in V, x,y \in T^* \end{array}\end{split}$

Each production has at most one variable, so the grammar is linear. The variables (B and C) are at the start of the RHS, so it is a left linear grammar.

OK, so now we have the definitions that we need to define a regular grammar.

Definition:

A regular grammar is a right-linear or left-linear grammar.

Example 1

$\begin{split}\begin{eqnarray*} G &=& (\{S\},\{a,b\},S,P),\\ P &=& \\ &&S \rightarrow abS \\ &&S \rightarrow \lambda \\ &&S \rightarrow Sab \\ \end{eqnarray*}\end{split}$

The language is $(ab)*$ .

However, cannot mix left/right rules! So this is not a regular grammar.

Example 2

$\begin{split}\begin{eqnarray*} G &=& (\{S\},\{a,b\},S,P),\\ P &=& \\ &&S \rightarrow aB | bS | \lambda \\ &&B \rightarrow aS | bB \\ \end{eqnarray*}\end{split}$

This is a right linear grammar representing the language $L = \{ \mbox{strings with an even number of a's}\}, \Sigma = \{a,b\}$

1.1. Our Next Step¶

What we have already done:

Definition: DFA represents regular language
Theorem: NFA ⟺ DFA
Theorem: RE ⟺ NFA

What we will do next:

Theorem: DFA

$\Longleftrightarrow$ regular grammar

1.2. NFA from Regular Grammar¶

Theorem: L is a regular language if and only if there exists a regular grammar $G$ such that $L = L(G)$ .

(Doing here for RR grammar)

( $\Longleftarrow$ ) Given a regular grammar G, Construct NFA M such that $L(G)=L(M)$

Make a state for each non-terminal.

Make a transition on each terminal in that production rule.

Make it final if there is a production without non-terminals.

For rules with multiple terminals, need intermediate states.

Example 3

S→aB|bS|λ
B→aS|bB

This is a right linear grammar representing the language

$L = \{$ strings with an even number of a’s

$\}, \Sigma = \{a,b\}$

What about a rule like $S \rightarrow abB$ ? Make two states (S to intermediate state on a, then intermediate state to B on b).

Or $S \rightarrow ab$ ? Make two states (S to intermediate state on a, then intermediate state to an accepting state on B.

1 / 10 Settings

<<<>>>

Suppose we need to convert this Regular Grammar to an NFA

Saving...

Server Error
Resubmit

1.3. Right-linear Regular Grammar from DFA¶

Theorem: L is a regular language if and only if there exists a regular grammar G such that $L = L(G)$ .

( $\Longrightarrow$ ) Given a DFA $M$ , construct regular grammar $G$ such that $L(G)=L(M)$

The process is pretty much the same as when we made an NFA from RRG:

Each DFA state gets a non-terminal.

Each transition gets a production rule.

Construct the Regular Grammar for the NFA

$G = (\{S,B\},\{a,b\},S,P)$ ,

$P =$

$Q0 \rightarrow a Q1$

$Q1 \rightarrow a Q0 | b Q1 | \lambda$

1 / 6 Settings

<<<>>>

Suppose we need to convert this NFA to a Regular Grammar

Saving...

Server Error
Resubmit

1.4. Something to Think About¶

Example 4

$L = \{a^nb^n \mid n>0\}$

Is language $L$ regular? Can you draw a DFA, regular expression, or Regular grammar for this language?

Consider this grammar:

$S \rightarrow aSb \mid ab$

Nice and easy… but this grammar is not regular!

We will come back to this question later.

OpenDSA Stand-alone Modules

Chapter 0 modules