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 of 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.

(There is a more restrictive definition in which the length of $x$ is $\leq 1$ .)

Example 1

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

$P =$

S→abS
S→λ
S→Sab

<< What language is this? >>

Example 1

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

$P =$

S→abS
S→λ
S→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 ⟺ DFA

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)$ .

(Doing here for RR grammar, see book for proof sketch for LR
grammar.)
(⟸) 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

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$ ? Or $S \rightarrow ab$ ?

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.

Example (1)

Construct the Regular Grammar for the NFA

Example (2)

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$

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?