Säännöllinen kieli
Siirry navigaatioon
Siirry hakuun
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.
Automaattiteoria: formaalit kielet ja formaalit kieliopit | |||
---|---|---|---|
Chomskyn hierarkia |
Kielioppi | Kieli | Tunnistusautomaatti |
luokka 0 | Rajoittamaton | Rekursiivisesti numeroituva | Turingin kone |
Rajoittamaton | Rekursiivinen | Totaalinen Turingin kone | |
luokka 1 | Yhteysherkkä | Yhteysherkkä | Lineaarisesti rajoitettu |
luokka 2 | Yhteydetön | Yhteydetön | Pinoautomaatti |
luokka 3 | Säännöllinen | Säännöllinen | Äärellinen |
Kukin luokka on sen yläpuolisen luokan aito osajoukko. |