Slide 1
Regular Grammars
Chapter 7
Grammars
A grammar G is a quadruple (V, , R, S), where:
● V is the rule alphabet, which contains nonterminals and terminals,
● (the set of terminals) is a subset of V,
● R is a finite set of rules of the form:
X Y, X,Y V*
● S V – — the start symbol
Regular Grammars
In a regular grammar, all rules in R must:
● have a left hand side that is a single nonterminal
● have a right hand side that is:
● , or
● a single terminal, or
● a single terminal followed by a single nonterminal.
Legal: S a, S , and T aS
Not legal: S aSa and aSa T
The language defined by a grammar: all terminal strings that can be obtained starting from S and applying the rules
Regular Grammar Example
L = {w {a, b}* : |w| is even} ((aa) (ab) (ba) (bb))*
Regular Grammar Example
L = {w {a, b}* : |w| is even} ((aa) (ab) (ba) (bb))*
Grammar:
S
S aT
S bT
T a
T b
T aS
T bS
Language:
S bT bb
S aT abS abbT
abbaS abba
S
Regular Languages and Regular Grammars
Theorem: The class of languages that can be defined with regular grammars is exactly the regular languages.
Proof: By two constructions.
Regular Languages and Regular Grammars
Regular grammar FSM:
grammartofsm(G = (V, , R, S)) =
1. Create in M a separate state for each nonterminal in V.
2. Start state is the state corresponding to S .
3. If there are any rules in R of the form X a, for some
a , create a new state labeled #.
4. For each rule of the form X a Y, add a transition from
X to Y labeled a.
5. For each rule of the form X a, add a transition from X
to # labeled a.
6. For each rule of the form X , mark state X as
accepting.
7. Mark state # as accepting.
FSM Regular grammar: Similarly.
Strings that End with aaaa
L = {w {a, b}* : w ends with the pattern aaaa}.
S aS
S bS
S aB
B aC
C aD
D a
Strings that End with aaaa
L = {w {a, b}* : w ends with the pattern aaaa}.
S aS
S bS
S aB
B aC
C aD
D a
Example 2 – One Character Missing
S A bA C aC
S aB A cA C bC
S aC A C
S bA B aB
S bC B cB
S cA B
S cB
Conversions
DFSM
NDFSM
Reg. Expressions
Reg. grammars
Minimal DFSM
subset constr.
Thompson
rip
Regular language
L