Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Strings that End with aaaaSlide 10Slide 11Regular GrammarsChapter 7Regular GrammarsA regular 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 (the set of rules) is a finite set of rules of the form: X  Y, ● S (the start symbol) is a nonterminal.Regular GrammarsIn 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  aSNot legal: S  aSa and aSa  TRegular 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))*S  S  aT S  bTT  aT  bT  aST  bSRegular Languages and Regular GrammarsTheorem: The class of languages that can be defined with regular grammars is exactly the regular languages. Proof: By two constructions.Regular Languages and Regular GrammarsRegular 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  w, for some w  , create a new state labeled #. 4. For each rule of the form X  w Y, add a transition from X to Y labeled w. 5. For each rule of the form X  w, add a transition from X to # labeled w. 6. For each rule of the form X  , mark state X as accepting. 7. Mark state # as accepting.FSM  Regular grammar: Similarly.Example 1 - Even Length Strings S   T  aS  aT T  bS  bT T  aS T  bSStrings that End with aaaaL = {w  {a, b}* : w ends with the pattern aaaa}. S  aSS  bS S  aBB  aCC  aDD  aStrings that End with aaaaL = {w  {a, b}* : w ends with the pattern aaaa}. S  aSS  bS S  aBB  aCC  aDD  aExample 2 – One Character MissingS   A  bA C  aCS  aB A  cA C  bCS  aC A   C  S  bA B  aBS  bC B  cBS  cA B  S 