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 λ.