title: Reguliere grammatica
text: Een reguliere grammatica is een formele grammatica (N, Σ, P, S) waarbij de productieregels aan een bepaalde  vorm voldoen. Een rechts-reguliere grammatica bevat productieregels die aan de rechterkant ten hoogste 1 niet-terminaal symbool bevatten dat alleen aan het einde mag voorkomen. Analoog hieraan bevat een links-reguliere grammatica alleen productieregels met aan de rechterkant ten hoogste 1 niet-terminaal symbool dat alleen aan het begin mag voorkomen.
  
  Definitie
  
  Formeel hebben de productieregels in een rechts-reguliere grammatica de volgende vorm:
  
   A → a - waarbij A een niet-terminaal symbool uit N is en a een terminaal symbool uit Σ
   A → aB - waarbij A en B uit N en a uit Σ
   A → ε - waarbij A uit N en ε geeft de lege string weer (een string met lengte 0)
  
  In een links-reguliere grammatica hebben alle productieregels de volgende vorm:
   A → a - waarbij A een niet-terminaal symbool uit N is en a een terminaal symbool uit Σ
   A → Ba - waarbij A en B uit N en a uit Σ
   A → ε - waarbij A uit N en ε de lege string is
  
  Kenmerken
  
  Reguliere grammatica's genereren de reguliere talen en zijn hierdoor equivalent aan eindigetoestandsautomaten en reguliere expressies. Zowel rechts-reguliere grammatica's als links-reguliere grammatica's zijn in staat alle reguliere talen te beschrijven. Elke reguliere grammatica is ook een context-vrije grammatica. Niet elke context-vrije grammatica is echter een reguliere grammatica. Daarnaast zijn er niet-reguliere talen (maar nog steeds context-vrije talen) die gebruikmaken van links- en rechts-reguliere productieregels; de context-vrije taal met de zinnen  wordt gegenereerd door de grammatica G met N = {S, A}, Σ = {a, b} en P:
  
   S → aA
   A → Sb
   S → ε
  
  en S het startsymbool. Deze grammatica bevat zowel links- als rechts-reguliere productieregels en is hierdoor niet meer regulier.
  
  Voorbeeld
  
  De volgende formele grammatica G met N = {S, A} en Σ = {a, b, c} is een rechts-reguliere grammatica. P bevat de volgende productieregels:
  
   S → aS
   S → bA
   A → ε
   A → cA
  
  Het startsymbool is S. Deze grammatica beschrijft dezelfde taal als de reguliere expressie a*bc*.
  
  Zie ook
  Reguliere taal
  Reguliere expressie
  
  Formele taal