Szabályos nyelvtan

A reguláris nyelvtan  egy 3. típusú formális nyelvtan a Chomsky-hierarchiában , a reguláris nyelvtan pontosan meghatározza az összes reguláris nyelvet , ezért egyenértékűek az állapotgépekkel és a reguláris kifejezésekkel . A reguláris nyelvtanok a környezetfüggetlen nyelvtanok egy részhalmazát képezik .

Szabálykészlet beállítása

Egy szabályos nyelvtant szabálykészlettel lehet megadni bal vagy jobb oldali szabályos nyelvtanként.

Jobb reguláris nyelvtan , vagy jobb- lineáris nyelvtan – minden szabály a következő formákban lehet:

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

bal oldali reguláris nyelvtan vagy bal- lineáris nyelvtan – minden szabály a következő formákban lehet:

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

ahol

A jobb és bal reguláris nyelvtan osztályai egyenértékűek – mindegyik külön-külön is elegendő az összes reguláris nyelv meghatározásához. Bármilyen szabályos nyelvtan konvertálható balról jobbra és fordítva.

Az alternatív nevek annak a ténynek köszönhető, hogy a lineáris nyelvtanok általánosabb osztályának alosztályai .

Példa

Az N = {S, A}, Σ = {a, b, c}, P által adott G jobb reguláris nyelvtan a következő szabályokból áll:

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

és S a kezdő szimbólum. Ez a nyelvtan ugyanazt a nyelvet írja le, mint az a*bc* reguláris kifejezés .

Korlátozott

Lényeges, hogy a szabályok vagy csak bal-regulárisak vagy csak jobb-regulárisak legyenek. A kettő kombinációja nem megengedett. Például egy környezetfüggetlen karakterlánc-nyelv, amelynek alakja nem reguláris, hanem egy G nyelvtan adja meg , ahol N = {S, A}, Σ = {a, b}, P a következőkből áll:

S→aA A→Sb S→ε

és S a kezdő szimbólum. Ez a nyelvtan bal-reguláris és jobb-reguláris szabályokat is tartalmaz , ezért nem szabályos.

Lásd még

Irodalom

 Formális nyelvek és formális nyelvtanok
Általános fogalmak
Típus 0
1. típus
2. típus
3. típus
elemzése