Reguliere grammatica

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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[bewerken]

Formeel hebben de productieregels in een rechts-reguliere grammatica de volgende vorm:

  1. Aa - waarbij A een niet-terminaal symbool uit N is en a een terminaal symbool uit Σ
  2. AaB - waarbij A en B uit N en a uit Σ
  3. 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:

  1. Aa - waarbij A een niet-terminaal symbool uit N is en a een terminaal symbool uit Σ
  2. ABa - waarbij A en B uit N en a uit Σ
  3. A → ε - waarbij A uit N en ε de lege string is

Kenmerken[bewerken]

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 gebruik maken van links- en rechts-reguliere productieregels; de context-vrije taal met de zinnen a^{i}b^{i} 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[bewerken]

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[bewerken]