Reguliere grammatica

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen

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