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 \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)\).
(Doing here for RR grammar, see book for proof sketch for LR
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.
<< What is the machine for Example 2? >>
RRG to NFA Example
\(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\)?
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?
