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 \(\Longleftrightarrow\) DFA
Theorem: RE \(\Longleftrightarrow\) 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 \rightarrow aB | bS | \lambda\)
\(B \rightarrow 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.

Settings

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\)

Settings

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