Säännöllinen kieli

Wikipediasta
Siirry navigaatioon Siirry hakuun

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 {ab} merkkijonoista, joissa on parillinen määrä merkkejä a.

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

Lähteet[muokkaa | muokkaa wikitekstiä]

  • 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.
Tämä tietotekniikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.