Formaali kieli

Formaali kieli on tietojenkäsittelytieteessä, matematiikassa ja logiikassa äärellisen pituisten merkkijonojen joukko, jotka on muodostettu jostakin äärellisestä aakkostosta.

On huomattava, että aakkoston on oltava äärellinen joukko merkkejä ja jokaisen merkkijonon pituuden on oltava äärellinen, mutta kieli voi hyvin sisältää äärettömän määrän merkkijonoja (koska kieleen sisältyvien merkkijonojen pituutta ei välttämättä ole rajoitettu).

Esimerkki aakkostosta on {a,b}, jolloin tämän aakkoston merkkijono voisi olla vaikkapa ababba. Tämän aakkoston tyypillinen kieli (joka sisältäisi kyseisen esimerkkijonon) olisi niiden merkkijonojen joukko, joissa on sama määrä merkkejä a ja b. Tyhjä merkkijono on merkkijono, jonka pituus on nolla. Sitä merkitään yleensä epsilonilla ε tai lambdalla λ.

Esimerkkejä

Esimerkkejä formaaleista kielistä:

• kaikkien aakkoston {a,b} merkkijonojen joukko
• joukko ${\displaystyle \scriptstyle \left\{a^{n}\right\}}$, missä n on luonnollinen luku (siis merkkijonot, joissa on n a:ta peräkkäin)
• jollakin ohjelmointikielellä kirjoitettujen ohjelmien joukko

Formaali kieli voidaan muodostaa useilla tavoilla, esimerkiksi sisällyttämällä siihen

• merkkijonot, jotka jokin formaali kielioppi tuottaa (katso Chomskyn hierarkia)
• merkkijonot, jotka jokin säännöllinen lauseke tuottaa
• merkkijonot, jotka tunnistaa jokin automaatti, esimerkiksi Turingin kone tai äärellinen automaatti

Operaatiot

Annetuista formaaleista kielistä voidaan tuottaa uusia kieliä useilla operaatioilla. Oletetaan, että A ja B ovat jonkin aakkoston kieliä.

• A:n ja B:n katenaatio AB koostuu kaikista muotoa vw olevista merkkijonoista, missä v on kielen A ja w kielen B merkkijono.
• A:n ja B:n leikkaus ${\displaystyle \scriptstyle A\cap B}$ koostuu niistä merkkijonoista, jotka ovat molemmissa kielissä A ja B.
• A:n ja B:n yhdiste ${\displaystyle \scriptstyle A\cup B}$ koostuu niistä merkkijonoista, jotka ovat jommassakummassa kielessä A tai B.
• Kielen A komplementti koostuu kaikista aakkoston merkkijonoista, jotka eivät kuulu kieleen A.
• Kielen A Kleenen tähti tai Kleenen sulkeuma A* koostuu kaikista merkkijonoista, jotka voidaan kirjoittaa muotoon ${\displaystyle \scriptstyle w_{1}w_{2}...w_{n}}$, missä merkkijono ${\displaystyle \scriptstyle w_{i}}$ kuuluu kieleen A ja ${\displaystyle \scriptstyle n\geq 0}$. Näin tuotettu kieli sisältää myös tyhjän merkkijonon ε, koska n voi olla nolla.

Aiheesta muualla

• Formal language theory: refining the Chomsky hierarchy (PDF) (englanniksi)
• Formal Language Theory (PDF) (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.