Tavallinen kielioppi

Säännöllinen kielioppi  on tyypin 3 formaali kielioppi Chomsky-hierarkiassa , säännölliset kieliopit määrittelevät tarkalleen kaikki säännölliset kielet ja vastaavat siten tilakoneita ja säännöllisiä lausekkeita . Tavalliset kieliopit ovat osa yhteydettömiä kielioppeja .

Sääntöjoukon asettaminen

Säännöllinen kielioppi voidaan määrittää säännöillä vasemman tai oikeanpuoleiseksi säännölliseksi kielioppiksi.

Oikea säännöllinen kielioppi tai oikea- lineaarinen kielioppi - kaikki säännöt voivat olla jossakin seuraavista muodoista:

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

vasen säännöllinen kielioppi tai vasen lineaarinen kielioppi - kaikki säännöt voivat olla jossakin seuraavista muodoista:

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

missä

• isot kirjaimet ( A , B ) tarkoittavat ei-päätteitä joukosta N
• pienet kirjaimet ( a , b ) tarkoittavat päätteitä joukosta Σ
• ε on tyhjä merkkijono, eli merkkijono, jonka pituus on 0

Oikean ja vasemman säännöllisen kieliopin luokat ovat samanarvoisia – kukin erikseen otettuna riittää määrittelemään kaikki säännölliset kielet. Mikä tahansa tavallinen kielioppi voidaan muuntaa vasemmalta oikealle ja päinvastoin.

Vaihtoehtoiset nimet johtuvat siitä, että ne ovat lineaaristen kielioppien yleisemmän luokan alaluokkia .

Esimerkki

Oikea säännöllinen kielioppi G , jonka N = {S, A}, Σ = {a, b, c}, P antaa, koostuu seuraavista säännöistä:

ja S on aloitussymboli. Tämä kielioppi kuvaa samaa kieltä kuin säännöllinen lauseke a*bc*.

Rajoitettu

On oleellista, että säännöt ovat joko vain vasen-säännöllisiä tai vain oikea-säännöllisiä. Molempien yhdistelmä ei ole sallittua. Esimerkiksi yhteydetön merkkijonokieli muodossa , jossa ei ole säännöllinen, vaan sen antaa kielioppi G , jossa N = {S, A}, Σ = {a, b}, P koostuu

ja S on aloitussymboli. Tämä kielioppi sisältää sekä vasen-säännölliset että oikeat-säännölliset säännöt, joten se ei ole säännöllinen.

Katso myös

• Säännölliset lausekkeet - muodollisten kielten teoriassa
• Etuliitteen kielioppi

Kirjallisuus

• Robin Hunter. Kääntäjän peruskäsitteet = Kääntäjien olemus. - M . : "Williams" , 2002. - S. 256. - ISBN 5-8459-0360-2 .
• Serebryakov V. A. , Galochkin M. P., Gonchar D. R., Furugyan M. G. Ohjelmointikielten teoria ja toteutus  - M.: MZ-Press, 2006, 2. painos. — ISBN 5-94073-094-9