Säännöllinen kieli

Säännöllinen kieli on formaali kieli, joka toteuttaa seuraavat keskenään ekvivalentit ehdot:

 se voidaan tunnistaa äärellisellä automaatilla, joko deterministisellä tai epädeterministisellä
 se voidaan kuvata säännöllisellä lausekkeella
 sen tuottaa jokin säännöllinen kielioppi (oikealle tai vasemmalle lineaarinen kielioppi)

Aakkoston Σ säännölliset kielet määritellään seuraavasti:
 tyhjä kieli Ø on säännöllinen
 kieli { ε } on säännöllinen (ε on tyhjä merkkijono)
 kaikilla a ∈ Σ kieli { a } on säännöllinen
 jos A ja B ovat säännöllisiä kieliä, myös A U B, AB ja A* ovat säännöllisiä
 muita Σ:n säännöllisiä kieliä ei ole

Kaikki äärelliset kielet (kielet, jotka sisältävät äärellisen määrän merkkijonoja) ovat säännöllisiä. Esimerkki äärettömästä säännöllisestä kielestä on kieli, joka koostuu kaikista sellaisista aakkoston {a, b} merkkijonoista, joissa on parillinen määrä merkkejä a.

Säännölliset kielet on yksinkertaisin luokka formaaleja kieliä luokittelevassa Chomskyn hierarkiassa.

Lähteet


Luokka:Formaalit kielet