Formellt språk

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.

Den här artikeln handlar om det tekniska begreppet i bland annat matematik och datorvetenskap. För det som vardagligt kallas formellt språk, se Kontrollerat språk.

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.

Se även

• Algoritm
• Formalvetenskap
• Kontrollerat språk
• Naturligt språk
• Formell grammatik

Externa länkar

• University of Maryland, Formal Language Definitions
• James Power, "Notes on Formal Language Theory and Parsing", 29 november 2002.
• Drafts of some chapters in the "Handbook of Formal Language Theory", Vol. 1-3, G. Rozenberg and A. Salomaa (eds.), Springer Verlag, (1997):t
  • Alexandru Mateescu and Arto Salomaa, "Preface" in Vol.1, pp. v-viii, and "Formal Languages: An Introduction and a Synopsis", Chapter 1 in Vol. 1, pp.1-39
  • Sheng Yu, "Regular Languages", Chapter 2 in Vol. 1
  • Jean-Michel Autebert, Jean Berstel, Luc Boasson, "Context-Free Languages and Push-Down Automata", Chapter 3 in Vol. 1
  • Christian Choffrut and Juhani Karhumäki, "Combinatorics of Words", Chapter 6 in Vol. 1
  • Tero Harju and Juhani Karhumäki, "Morphisms", Chapter 7 in Vol. 1, pp. 439 - 510
  • Jean-Eric Pin, "Syntactic semigroups", Chapter 10 in Vol. 1, pp. 679-746
  • M. Crochemore and C. Hancart, "Automata for matching patterns", Chapter 9 in Vol. 2
  • Dora Giammarresi, Antonio Restivo, "Two-dimensional Languages", Chapter 4 in Vol. 3, pp. 215 - 267