2.2. Regular Grammars¶
2.2.1. 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.
2.2.2. 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.
2.2.3. 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\).)
2.2.4. Example 1¶
\(G = (\{S\},\{a,b\},S,P),\)\(P =\)\(S \rightarrow abS\)\(S \rightarrow \lambda\)\(S \rightarrow Sab\)<< What language is this? >>
2.2.5. 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.
2.2.6. 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? >>
2.2.7. 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\}\)
2.2.8. Our Next Step¶
Done before:Definition: DFA represents regular languageTheorem: RE \(\Longleftrightarrow\) DFANext:Theorem: DFA \(\Longleftrightarrow\) regular grammarTheorem: L is a regular language iff \(\exists\) regular grammar G such that \(L = L(G)\).
2.2.9. 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? >>
2.2.10. RRG to NFA Example¶
<< See 4.4.2 >>
2.2.11. 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.
2.2.12. NFA to RRG Example¶
<<See 4.4.3>>
2.2.13. 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?
