Almindelig grammatik

En regulær grammatik  er en formel grammatik af type 3 i Chomsky-hierarkiet , regulære grammatikker definerer præcis alle regulære sprog , og er derfor ækvivalente med tilstandsmaskiner og regulære udtryk . Almindelige grammatikker er en delmængde af kontekstfri grammatik .

Indstilling af et sæt regler

En regulær grammatik kan specificeres af et sæt regler som en venstre eller højre regulær grammatik.

Højre regulær grammatik eller højre- lineær grammatik - alle regler kan være i en af ​​følgende former:

  1. A → a
  2. A → aB
  3. A →ε

venstre regulær grammatik , eller venstre- lineær grammatik , - alle regler kan være i en af ​​følgende former:

  1. A → a
  2. A → Ba
  3. A →ε

hvor

Klasserne af højre og venstre regulære grammatikker er ækvivalente - hver taget separat er tilstrækkelig til at definere alle regulære sprog. Enhver almindelig grammatik kan konverteres fra venstre til højre og omvendt.

De alternative navne skyldes, at de er underklasser af den mere generelle klasse af lineære grammatikker .

Eksempel

Den rigtige regulære grammatik G givet af N = {S, A}, Σ = {a, b, c}, P består af følgende regler:

S → aS S→bA A→ε A→cA

og S er startsymbolet. Denne grammatik beskriver det samme sprog som det regulære udtryk a*bc*.

Begrænset

Det er væsentligt, at reglerne enten kun skal være venstre-regulære eller kun højre-regulære. En kombination af begge er ikke tilladt. For eksempel et kontekstfrit strengsprog af formen , hvor er ikke regulært, men er givet af en grammatik G , hvor N = {S, A}, Σ = {a, b}, P består af

S→aA A→Sb S→ε

og S er startsymbolet. Denne grammatik indeholder både venstre-regulære og højre-regulære regler, og er derfor ikke regulære.

Se også

Litteratur

 Formelle sprog og formelle grammatikker
Generelle begreber
Type 0
Type 1
Type 2
Type 3
parsing