Tähestik, sõna, keel

Transleerimine on lähteteksti (transleeritava programmi teksti, s.t. märgijada) teisendamine objekttekstiks - mingis teises programmeerimiskeeles kirjutatud tekstiks, s.t. teistsuguseks märgijadaks. Selliseid märgijadade hulki (näiteks kõikvõimalike korrektsete programmide hulka mingis programmeerimiskeeles) nimetatakse märgikeeleks (character language).

Märgikeele kirjeldamine algab keeles lubatud sümbolite, s.t. keele tähtestiku defineerimisega.
Tähestik on lõplik hulk üksteisest eristatavaid sümboleid. Tähestiku esitamisel vajatakse ka metasümboleid (abisümboleid, tähestikku mitte kuuluvaid sümboleid), näiteks {0,1} on binaarsümbolitest 0,1 koosnev kaheelemendiline tähestik, mille esitamisel on kasutatud metasümboleid ''{', ' }', ' ,' (loogelised sulud ja koma). Metasümbolitel on alati mingi interpretatsioon, näiteks loogelised sulud piiravad hulga elementide loetelu, koma on eraldajaks hulge elementide vahel jne ja nad ei kuulu tähestikku. Ka tähestikku kuuluvates sümbolitel võib mõnikord olla interpretatsioon (semantika), näiteks \n tähendab paljudes programmeerimiskeeltes uuele reale siirdumist jne, kuid see pole märgikeelte käsitlemisel tavaliselt oluline (see on väga oluline nende keelte kasutamisel arvutis). Kui keelde kuuluvate märkide (tähtede) esitamisel (näiteks arvutis tekstina) on oht, et neid interpreteeritakse (näiteks operatsioonisüsteemi poolt), esitatakse nad kas apostroofide ' ' (märgi esitamisviis paljudes programmeerimiskeeltes) või jutummärkide " " (stringi esitamisviis programmeerimiskeeltes) vahel. Mingi lihtsa programmeerimiskeele tähestik võiks näiteks olla

T = {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,
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ühik).

Sõna (antud tähestikus) on igasugune selle tähestiku tähtedest moodustatud jada, näiteks a, aasd, a9Fa-q on sõnad tähestikus T; ka tühi sõna on sõna. T* on kõigi sõnade hulk tähestikus T, T+ = T* \ , st. T+ on kõigi mittetühjade sõnade hulk. T2 = TT , st. T2 on kõigi kahetäheliste sõnade hulk. Sõna w pikkust tähistatakse l(w) , näiteks l(vwc) = 3; la(w) on tähe a esinemiste arv sõnas w , näiteks lt(mitte) = 2.

Teoreem : T* = T U T 2 U T 3 U ...

Keel on mingi kõigi sõnade hulga T * alamhulk (seega keel on sõnade hulk). Formaalsete keelte teooria tegeleb (lõpmatute) keelte genereerimismehhanismide (formaalsete grammatikate ) ja tunnistamismehhanismide (abstraktsete automaatide ) uurimisega.

Genereerimismehhanism (grammatika) on algoritm, mis suudab genereerida (moodustada) kõik keelde kuuluvad sõnad (ja ainult need); eespool oli näitena 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äiteks programmeerimiskeele translaator on tunnistamismehhanism, mis tunneb ära korrektsed (süntaksivigadeta) programmid; translaatori poolt tunnistatav keel koosneb kõigist selles programmeerimiskeeles kirjutatud korrektsetest (süntaksivigadeta) programmidest; iga selline programm on sõna selles keeles.


Ülesandeid:
1. Ylesande tekst

Küsimused, probleemid: ©2004 Jaak Henno