Tähestik, sõna, keel

Märgikeele kirjeldamine algab keele väljendites (sõnades ja lausetes) lubatud sümbolite, s.t. tähtestiku defineerimisega.
Tähestik on lõplik hulk üksteisest eristatavaid sümboleid; tähestiku (tähtede hulga) esitamisel kasutatakse tavaliselt metasümboleid (s.t. tähestikku mitte kuuluvaid sümboleid) { , } ja " ", seega näiteks {0,1} on binaarsümbolitest 0,1 koosnev kaheelemendiline tähestik. Et metasümboli , kasutamine hulga elementide eraldajana ei tekitaks segadust, esitatakse tähestikku kuuluvad märgid (. , - ; jne) tavaliselt jutumärkide vahel (seega ka jutumärgid on siin metasümbolid, s.t. ei kuulu tähestikku); näiteks programeerimiskeele tähestik võiks olla
{0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,Õ,Ä,Ö,Ü,X,Y,Z, ",", ".", "-",";",""}
( tähistab tühikut).
Sõna (antud tähestikus) on igasugune selle tähestiku tähtedest moodustatud jada, näiteks: a, aasd, aDFadqDadADQDA on sõnad; ka tühi sõna on sõna. A* on kõigi sõnade hulk tähestikus A, A⁺ = A*\ , st. A⁺ on kõigi mittetühjade sõnade hulk. A² = AA, st. A² on kõigi kahetäheliste sõnade hulk Sõna w pikkust tähistatakse l(w), näit. l(vwc) = 3; l_a(w) on tähe "a" esinemiste arv sõnas w, näiteks l_t(mitte) = 2.

Teoreem: A*= A U A² U A³ U ...

Keel on mingi kõigi sõnade hulga A^* alamhulk (seega keel on sõnade hulk ). Formaalsete keelte teooria tegeleb lõpmatute keelte: genereerimismehhanismide (formaalsete grammatikate) ja tunnistamismehhanismide (abstraktsete automaatide) uurimisega. Genereerimismehhanism (e. grammatika) on algoritm, mis suudab genereerida (moodustada) kõik keelde kuuluvad sõnad (ja ainult need); eespool olid toodud eesti keele lihtlause genereerimismehhanism ja lihtsa programmeerimiskeele programmide genereerimismehhanism. Tunnistamismehhanism on algoritm, mis mingi sõna w ja keele L jaoks (mõlemad samas tähestikus) suudab vastata küsimusele: w L ?

Näide 1. Olgu tähestik {0,1}, siis genereerimismehhanism
algus = 0
algus = algus 00
sõna = algus 1
annab üldmõiste "sõna" väärtuseks jadad 01, 0001, 000001, 00000001 jne

1. Kirjelda genereerimismehhanism, mis genereerib kõik kahendsüsteemis kirjutatud paaris täisarvud.
2. Kirjelda genereerimismehhanism, mis genereerib kõik korrektselt kirjeldatud matemaatilised avaldised, kus on kasutatud kahendsüsteemis kirjutatud arve ja nelja aritmeetilist tehet.