2.Regular Grammarsยง

Here is another way to describe a language: Use a grammar.

Grammar \(G = (V, T, S, P)\)

\(V\): Variables (nonterminals), represented by \(A, B, ..., Z\)
\(T\): Terminals, reprsented by \(a, b, ..., z, 0, 1, ..., 9\)
\(S\): Start symbol
\(P\): Productions (rules)

\(V\), \(T\), and \(P\) are finite sets.

Right-linear grammar

All productions are of the form:
\(A \rightarrow xB\)
\(A \rightarrow x\)
where \(A, B \in V, x \in T^*\)

Note: \(x\) is a string of length 0 or more.

Left-linear grammar

All productions are of the form:
\(A \rightarrow Bx\)
\(A \rightarrow x\)
where \(A, B \in V, x \in T^*\)

Definition:

Any right-linear or left-linear grammar is defined to be a regular grammar.

(Some books use a more restrictive definition in which the length of \(x\) is \(\leq 1\).)

Example 1

\(G = (\{S\},\{a,b\},S,P),\)
\(P =\)
\(S \rightarrow abS\)
\(S \rightarrow \lambda\)
\(S \rightarrow Sab\)

<< What language is this? >>

Example 1

\(G = (\{S\},\{a,b\},S,P),\)
\(P =\)
\(S \rightarrow abS\)
\(S \rightarrow \lambda\)
\(S \rightarrow Sab\)

Cannot mix left/right rules! This is not a regular grammar.

Example 2

\(G = (\{S\},\{a,b\},S,P),\)
\(P =\)
\(S \rightarrow aB \mid bS \mid \lambda\)
\(B \rightarrow aS \mid bB\)

<< What language is this? >>

Example 2

\(G = (\{S\},\{a,b\},S,P),\)
\(P =\)
\(S \rightarrow aB \mid bS \mid \lambda\)
\(B \rightarrow aS \mid bB\)

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

Our Next Step

Done before:
Definition: DFA represents regular language
Theorem: RE \(\Longleftrightarrow\) DFA

Next:
Theorem: DFA \(\Longleftrightarrow\) regular grammar

Theorem: L is a regular language iff \(\exists\) regular grammar G such that \(L = L(G)\).

Proof: NFA from Regular Grammar

Theorem: L is a regular language iff \(\exists\) regular grammar G such that \(L = L(G)\).

(\(\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.

<< What is the machine for Example 2? >>

RRG to NFA Example

<< See 4.4.2 >>

Proof: RR Grammar from DFA

Theorem: L is a regular language iff \(\exists\) 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.

NFA to RRG Example

<<See 4.4.3>>

Something to Think About

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

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