Formellt språk

Den här artikeln behöver källhänvisningar för att kunna verifieras. (2014-05) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan.

Ett formellt språk är en mängd ord över ett alfabet Σ. Ett alfabet består av en mängd symboler, t.ex. Σ = {1,2,3,4,5,6,7,8,9,0} och ett ord består av en sträng av alfabetets symboler, här exempelvis "0124311". Ett formellt språk är alltså en mängd av sådana strängar (ord) som i sin tur endast innehåller symboler ur det formella språkets alfabet.

Ett formellt språk är en delmängd av Σ*, där Σ* är alla möjliga kombinationer av strängar över alfabetet Σ.

Ett formellt språk (dvs vilka ord språket innehåller) kan definieras med exempelvis explicita grammatiska regler för hur språkets symboler får kombineras (därmed har man en delmängd av Σ*), men dessa regler skall inte förväxlas med det formella språket självt som ju är varken mer eller mindre än en mängd ord. Om frasen F="över alfabetet {0,a,b,c} så är ett ord en nolla och sedan a eller b eller c" beskriver det formella språket L = {"0a", "0b","0c"} så är L ett formellt språk och F en informell definition/beskrivning av L. Även om det finns en koppling mellan dem så skall de särskiljas: F är alltså inte en del av det formella språket.

Ett formellt språk kan definieras på många sätt, exempel:

• Informellt, beskrivet med ord. Exempel: "alla strängar av längd 4 enbart innehållandes symbolen a". Det formella språket innehåller då bara ordet "aaaa".
• Definiera språkets ord direkt. Exempel: L = {apa,hund,1,0}
• Med reguljära uttryck. Exempel: [a-z]|321. Detta implicerar L = {a,b,..,x,y,z,321}
• Godtyckligt: som siffrorna i antalet munkar Gösta bakade år 1733.

Formella språk används inom logik och matematik, men framförallt i datorsammanhang. Programmeringsspråk för datorer har implicit ett formellt språk eftersom ett programmeringsspråks syntax implicerar en (typiskt oändlig) mängd L av giltiga källkoder.