Formalni jezik

Formalni jezik je skup reči, to jest konačnih niski slova, ili simbola. Skup iz koga se ova slova uzimaju se naziva azbukom nad kojom je jezik definisan. Formalni jezik se često definiše pomoću formalne gramatike. Formalni jezici su čisto sintaksni pojam, tako da nije obavezno da postoji neko značenje povezano sa njima. Kako bi se razlikovale reči koje pripadaju jeziku od proizvoljnih reči nad datom azbukom, reči koje pripadaju jeziku se ponekad nazivaju dobro-formiranim rečima (ili kada se radi o primenama u logici, dobro-formiranim formulama).

Formalni jezici se proučavaju u oblastima logike, računarstva i lingvistike. Njihova najvažnija primena je u preciznom definisanju sintaksno ispravnih programa za programski jezik. Grana matematike i računarstva koja se bavi samo sintaksnim aspektima takvih jezika, to jest njihovim strukturnim obrascima, se naziva teorija formalnih jezika.

Mada to u užem smislu nije deo jezika, reči formalnog jezika često imaju i semantičku dimenziju. U praksi je ovo uvek u vrlo čvrstoj vezi sa strukturom jezika, i formalna gramatika (skup pravila za izvođenje koji rekurzivno opisuju jezik) može da pomogne u razumevanju značenja (dobro-formiranih) reči. Dobro poznati primeri za ovo su definicija istine Tarskog u okvirima T-sheme za logiku prvog reda, i generatori kompajlera kao što su lex i yacc.

Reči nad azbukom

Azbuka, u kontekstu formalnog jezika može da bude bilo koji skup, mada često ima smisla da se koristi azbuka u uobičajenom smislu reči, ili opštije skup karaktera, kao što je aski. Azbuke su često beskonačne; na primer logika prvog reda je često izražena korišćenjem azbuke koaj pored simbola ∧, ¬, ∀ i zagrada sadrži i beskonačno mnogo elemenata x₀, x₁, x₂, … koji vrše funkciju promenljivih. Elementi azbuke se nazivaju njenim slovima.

Reč nad azbukom može da bude bilo koji konačni niz ili niska, njenih slova. Skup svih reči nad azbukom Σ se obično označava kao Σ^* (Klinijeva zvezda). Za bilo koju azbuku postoji samo jedna reč dužine 0, prazna reč, koja se često označava simbolima e, ε ili λ. Konkatenacijom (dopisivanjem) mogu da se kombinuju dve reči kako bi dale novu reč, čija je dužina jednaka zbiru dužina početnih reči. Rezultat konkatenacije bilo koje reči sa praznom rečju je ta ista reč.

U nekim primenama, posebno u logici, azbuka je poznata i kao rečnik a reči su poznate kao formule ili rečenice; ovo prekida metaforu slovo/reč i zamenjuje je metaforom reč/rečenica

Definicija

Formalni jezik L nad azbukom Σ je samo podskup od Σ^*, to jest, skup reči nad azbukom.

U računarstvu i matematici, koji se ne bave prirodnim jezicima, pridev formalni se često ne koristi već se podrazumeva.

Iako se teorija formalnih jezika uglavnom bavi formalnim jezicima koji su opisani nekim sintaksnim pravilima, stvarna definicia formalnog jezika je upravo ona data iznad: (moguće beskonačan) skup niski konačne dužine. Ništa više od toga, ništa manje od toga. Međutim, u praksi postoji mnogo jezika koji mogu da budu opisani pravilima, kao što su regularni jezici ili kontekstno-slobodni jezici. Pojam formalne gramatike može biti bliži intuitivnom pojmu jezika, opisanog sintaksnim pravilima. Zloupotrebom definicije, za određeni formalni jezik se često smatra da poseduje formalnu gramatiku koja ga opisuje.

Primeri

Sledeća pravila opisuju formalni jezik L nad azbukom Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, =}:

• Svaka neprazna niska koja ne sadrži + ili = i ne počinje simbolom 0 je u L.
• Niska 0 je u L.
• Niska koja sadrži = je u L ako i samo ako postoji tačno jedno =, koje razdvaja dve validne niske u L.
• Niska koja sadrži + ali ne i = je u L ako i samo ako svako + u niski razdvaja dve validne niske u L.
• Nijedna niska koja nije opisana prethodnim pravilima nije u L.

Po ovim pravilima, niska 23+4=555 je u L, ali niska =234=+ nije. Ovaj formalni jezik izražava prirodne brojeve, dobro formirane iskaze sabiranja, i dobro formirane jednakosti sabiranja, ali on izražava samo kako ovi izrazi izgledaju (njihovu sintaksu), a ne govori ništa o njihovom značenju (semantici). Na primer, nigde u ovim pravilima ne postoji nikakva naznaka da 0 predstavlja broj nula ili da + označava sabiranje.

Kod konačnih jezika je moguće prosto nabrojati sve dobro formirane reči. Na primer, možemo da opišemo jezik L kao L = {a, b, ab, cba}.

Međutim, i nad konačnom (nepraznom) azbukom kao što je Σ = {a, b} postoji beskonačno mnogo reči: a, abb, ababba, aaababbbbaab, …. Dakle, formalni jezici su obično beskonačni, a opisivanje beskonačnog formalnog jezika nije jednostavno kao zapisivanje L = {a, b, ab, cba}. Slede neki primeri formalnih jezika:

• L = Σ^*, skup svih reči nad Σ;
• L = {a}^* = {aⁿ}, gde je n neki prirodan broj a aⁿ znači a ponovljeno n puta (ovo je skup svih reči koje se sastoje samo od simbola a);
• skup svih sintaksno ispravnih programa u datom programskom jeziku (čija sintaksa je obično definisana kontekstno-slobodnom gramatikom;
• skup ulaza za koje određena Tjuringova mašina staje; ili
• skup maksimalnih niski alfanumeričkih karaktera u ovom redu, (to jest skup {skup, maksimalnih, niski, alfanumeričkih, karaktera, u, ovom, redu, to, jest}).

Jezičko-specifični formalizmi

Teorija formalnih jezika se retko bavi pojedinačnim jezicima (osim kao primerima), već se uglavnom bavi proučavanjem različitih vrsta formalizama za opisivanje jezika. Na primer, jezik može da bude dat kao

• one niske generisane nekom formalnom gramatikom (vidi hijerarhija Čomskog);
• one niske opisane određenim regularnim izrazom;
• one niske koje prihvata neki automat, kao što je Tjuringova mašina ili končani automat;
• one niske za koje neka procedura odlučivanja (algoritam koji postavlja niz povezanih DA/NE pitanja) daje odgovor DA.

Tipična pitanja koja se postavljaju u vezi sa ovim formalizmima su:

• Koja je njihova izražajna moć? (Može li formalizam X da opiše svaki jezik koji formalizam Y može da opiše? Može li da opiše i neke druge jezike?)
• Kolika je njihova prepoznatljivost? (Koliko je teško da se odredi da li data reč pripada jeziku koji opisuje formalizam X?)
• Kakva je njihova uporedljivost? (Koliko je teško da se odredi da li su dva jezika, jedan opisan formalizmom X a drugi opisan formalizmom -{Y-, ili takođe formalizmom X, u stvari isti jezik?).

Vrlo često je odgovor na ovakve probleme odlučivanja: to ne može da se uradi, ili: to bi bilo izuzetno skupo (sa preciznom odrednicom šta se tačno misli pod skupo). Stoga, teorija formalnih jezika je glavna oblast primene teorije izračunljivosti i teorije kompleksnosti.

Operacije nad jezicima

Izvesne operacije nad jezicima su uobičajene. One uključuju standardni skup operacija kao što su unija, presek i komplement. Druga klasa operacija su operacije nad niskama koje se primenjuju na elemente.

Primeri: neka su L₁ i L₂ jezici nad nekom uobičajenom azbukom.

• Konkatenacija L₁L₂ se sastoji od svih niski oblika vw gde je v niska jezika L₁ dok je w niska jezika L₂.
• Presek L₁ ∩ L₂ jezika L₁ i L₂ se sastoji od svih niski koje se nalaze u oba jezika.
• Komplement ¬L jezika u odnosu na datu azbuku se sastoji od svih niski nad tom azbukom koje nisu u jeziku L.
• Klinijeva zvezda: jezik koji se sastoji od svih reči koje su konkatenacija nula ili više reči početnog jezika;
• Obrat:
  • Neka je e prazna niska. Tada je e^R = e, i
  • za svaku nepraznu reč w = x₁…x_n nad nekom azbukom, neka je w^R = x_n…x₁,
  • tada za formalni jezik L,  w ∈ L}.
• Homomorfizam niski.

Takve operacije nad niskama se koriste za izučavanje svojstava zatvorenja klasa jezika. Klasa jezika je zatvorena u odnosu na određenu operaciju, kada ako se operacija primeni na jezike te klase, uvek daje jezike koji pripadaju istoj toj klasi. Na primer, kontekstno-slobodni jezici su zatvoreni u odnosu na uniju, konkatenaciju i presek sa regularnim jezicima, ali nisu zatvoreni za presek ili komplement.

Svojstva zatvorenja familija jezika ($L_{1}$ operator $L_{2}$ gde i $L_{1}$ i $L_{2}$ pripadaju familiji jezika naznačenoj na vrhu kolone). Dato po Hopkroftu i Ulmanu.

Operacija		regularan	DKSJ	KSJ	KOJ	rekurzivan	r. p.
unija	$\{w|w\in L_{1}\lor w\in L_{2}\}$	Da	Ne	Da	Da	Da	Da
presek	$\{w|w\in L_{1}\land w\in L_{2}\}$	Da	Ne	Ne	Da	Da	Da
komplement	$\{w|w\not \in L_{1}\}$	Da	Da	Ne	Da	Da	Ne
konkatenacija	$L_{1}\cdot L_{2}=\{w\cdot z|w\in L_{1}\land z\in L_{2}\}$	Da	Ne	Da	Da	Da	Da
Klinijeva zvezda	$L_{1}^{*}=\{\epsilon \}\cup \{w\cdot z|w\in L_{1}\land z\in L_{1}^{*}\}$	Da	Ne	Da	Da	Da	Da
homomorfizam		Da	Ne	Da	Ne	Ne	Da
e-slobodan homomorfizam		Da	Ne	Da	Da	Da	Da
supstitucija		Da	Ne	Da	Da	Ne	Da
inverzni homomorfizam		Da	Da	Da	Da	Da	Da
obrat	$\{w^{R}|w\in L\}$	Da	Ne	Da	Da	Da	Da
presek sa regularnim jezikom	$\{w|w\in L_{1}\land w\in R,R{\text{ regular}}\}$	Da	Da	Da	Da	Da	Da

Vidi još

• Azbuka (računarstvo)
• Formalna gramatika
• Formalni metod
• Formalna nauka
• Formalni sistem
• Matematička notacija
• Programski jezik

Reference

• A. G. Hamilton (1978). Logic for Mathematicians. Cambridge University Press. ISBN 978-0-521-21838-2. .
• Seymour Ginsburg, Algebraic and automata theoretic properties of formal languages, North-Holland. 1975. ISBN 978-0-7204-2506-2..
• Michael A. Harrison, Introduction to Formal Language Theory, Addison-Wesley, 1978.
• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing, Reading Massachusetts. 1979. ISBN 0-201-029880-X ..
• Grzegorz Rozenberg, Arto Salomaa (1997). Handbook of Formal Languages: Volume I-III. Springer. ISBN 978-3-540-61486-9. .
• Patrick Suppes, Introduction to Logic, D. Van Nostrand. 1957. ISBN 978-0-442-08072-3..

Spoljašnje veze

• Azbuka na sajtu PlanetMath
• Jezik na sajtu PlanetMath
• Univerzitet Merilenda, Definicije formalnih jezika
• Džejms Pauer, Beleške o teoriji formalnih jezika i parsiranju Arhivirano na sajtu Wayback Machine (21. novembar 2007), 29. novembar 2002.
• Nacrti nekih poglavlja iz Udžbenika teorije formalnih jezika, tomovi 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