Formaali kieli

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

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.

• Formal language theory: refining the Chomsky hierarchy (PDF) (englanniksi)
• Formal Language Theory (PDF) (englanniksi)