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
- Sipser, Michael: Introduction to the theory of computation. 3rd Ed.. Boston, MA: Cengage Learning, 2013. ISBN 978-1-133-18779-0. (englanniksi)
| 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. | |||
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.