Säännöllinen kieli on formaali kieli, joka toteuttaa seuraavat keskenään ekvivalentit ehdot:
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
- Sipser, Michael: Introduction to the theory of computation. (3rd Ed.) Boston, MA: Cengage Learning, 2013. ISBN 978-1-133-18779-0 (englanniksi)
