Reguliere grammatica

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:

1. A → a - waarbij A een niet-terminaal symbool uit N is en a een terminaal symbool uit Σ
2. A → aB - 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. A → a - waarbij A een niet-terminaal symbool uit N is en a een terminaal symbool uit Σ
2. A → Ba - waarbij A en B uit N en a uit Σ
3. 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 $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

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