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

(⟸) 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?