Формални језик

Формални језик је скуп речи, то јест коначних ниски слова, или симбола. Скуп из кога се ова слова узимају се назива азбуком над којом је језик дефинисан. Формални језик се често дефинише помоћу формалне граматике. Формални језици су чисто синтаксни појам, тако да није обавезно да постоји неко значење повезано са њима. Како би се разликовале речи које припадају језику од произвољних речи над датом азбуком, речи које припадају језику се понекад називају добро-формираним речима (или када се ради о применама у логици, добро-формираним формулама).

Формални језици се проучавају у областима логике, рачунарства и лингвистике. Њихова најважнија примена је у прецизном дефинисању синтаксно исправних програма за програмски језик. Грана математике и рачунарства која се бави само синтаксним аспектима таквих језика, то јест њиховим структурним обрасцима, се назива теорија формалних језика.

Мада то у ужем смислу није део језика, речи формалног језика често имају и семантичку димензију. У пракси је ово увек у врло чврстој вези са структуром језика, и формална граматика (скуп правила за извођење који рекурзивно описују језик) може да помогне у разумевању значења (добро-формираних) речи. Добро познати примери за ово су дефиниција истине Тарског у оквирима Т-схеме за логику првог реда, и генератори компајлера као што су lex и yacc.

Речи над азбуком

Азбука, у контексту формалног језика може да буде било који скуп, мада често има смисла да се користи азбука у уобичајеном смислу речи, или општије скуп карактера, као што је аски. Азбуке су често бесконачне; на пример логика првог реда је често изражена коришћењем азбуке коај поред симбола ∧, ¬, ∀ и заграда садржи и бесконачно много елемената x₀, x₁, x₂, … који врше функцију променљивих. Елементи азбуке се називају њеним словима.

Реч над азбуком може да буде било који коначни низ или ниска, њених слова. Скуп свих речи над азбуком Σ се обично означава као Σ^* (Клинијева звезда). За било коју азбуку постоји само једна реч дужине 0, празна реч, која се често означава симболима e, ε или λ. Конкатенацијом (дописивањем) могу да се комбинују две речи како би дале нову реч, чија је дужина једнака збиру дужина почетних речи. Резултат конкатенације било које речи са празном речју је та иста реч.

У неким применама, посебно у логици, азбука је позната и као речник а речи су познате као формуле или реченице; ово прекида метафору слово/реч и замењује је метафором реч/реченица

Дефиниција

Формални језик L над азбуком Σ је само подскуп од Σ^*, то јест, скуп речи над азбуком.

У рачунарству и математици, који се не баве природним језицима, придев формални се често не користи већ се подразумева.

Иако се теорија формалних језика углавном бави формалним језицима који су описани неким синтаксним правилима, стварна дефинициа формалног језика је управо она дата изнад: (могуће бесконачан) скуп ниски коначне дужине. Ништа више од тога, ништа мање од тога. Међутим, у пракси постоји много језика који могу да буду описани правилима, као што су регуларни језици или контекстно-слободни језици. Појам формалне граматике може бити ближи интуитивном појму језика, описаног синтаксним правилима. Злоупотребом дефиниције, за одређени формални језик се често сматра да поседује формалну граматику која га описује.

Примери

Следећа правила описују формални језик L над азбуком Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, =}:

• Свака непразна ниска која не садржи + или = и не почиње симболом 0 је у L.
• Ниска 0 је у L.
• Ниска која садржи = је у L ако и само ако постоји тачно једно =, које раздваја две валидне ниске у L.
• Ниска која садржи + али не и = је у L ако и само ако свако + у ниски раздваја две валидне ниске у L.
• Ниједна ниска која није описана претходним правилима није у L.

По овим правилима, ниска 23+4=555 је у L, али ниска =234=+ није. Овај формални језик изражава природне бројеве, добро формиране исказе сабирања, и добро формиране једнакости сабирања, али он изражава само како ови изрази изгледају (њихову синтаксу), а не говори ништа о њиховом значењу (семантици). На пример, нигде у овим правилима не постоји никаква назнака да 0 представља број нула или да + означава сабирање.

Код коначних језика је могуће просто набројати све добро формиране речи. На пример, можемо да опишемо језик L као L = {a, b, ab, cba}.

Међутим, и над коначном (непразном) азбуком као што је Σ = {a, b} постоји бесконачно много речи: a, abb, ababba, aaababbbbaab, …. Дакле, формални језици су обично бесконачни, а описивање бесконачног формалног језика није једноставно као записивање L = {a, b, ab, cba}. Следе неки примери формалних језика:

• L = Σ^*, скуп свих речи над Σ;
• L = {a}^* = {aⁿ}, где је n неки природан број а aⁿ значи a поновљено n пута (ово је скуп свих речи које се састоје само од симбола a);
• скуп свих синтаксно исправних програма у датом програмском језику (чија синтакса је обично дефинисана контекстно-слободном граматиком;
• скуп улаза за које одређена Тјурингова машина стаје; или
• скуп максималних ниски алфанумеричких карактера у овом реду, (то јест скуп {скуп, максималних, ниски, алфанумеричких, карактера, у, овом, реду, то, јест}).

Језичко-специфични формализми

Теорија формалних језика се ретко бави појединачним језицима (осим као примерима), већ се углавном бави проучавањем различитих врста формализама за описивање језика. На пример, језик може да буде дат као

• оне ниске генерисане неком формалном граматиком (види хијерархија Чомског);
• оне ниске описане одређеним регуларним изразом;
• оне ниске које прихвата неки аутомат, као што је Тјурингова машина или кончани аутомат;
• оне ниске за које нека процедура одлучивања (алгоритам који поставља низ повезаних ДА/НЕ питања) даје одговор ДА.

Типична питања која се постављају у вези са овим формализмима су:

• Која је њихова изражајна моћ? (Може ли формализам X да опише сваки језик који формализам Y може да опише? Може ли да опише и неке друге језике?)
• Колика је њихова препознатљивост? (Колико је тешко да се одреди да ли дата реч припада језику који описује формализам X?)
• Каква је њихова упоредљивост? (Колико је тешко да се одреди да ли су два језика, један описан формализмом X а други описан формализмом -{Y-, или такође формализмом X, у ствари исти језик?).

Врло често је одговор на овакве проблеме одлучивања: то не може да се уради, или: то би било изузетно скупо (са прецизном одредницом шта се тачно мисли под скупо). Стога, теорија формалних језика је главна област примене теорије израчунљивости и теорије комплексности.

Операције над језицима

Извесне операције над језицима су уобичајене. Оне укључују стандардни скуп операција као што су унија, пресек и комплемент. Друга класа операција су операције над нискама које се примењују на елементе.

Примери: нека су L₁ и L₂ језици над неком уобичајеном азбуком.

• Конкатенација L₁L₂ се састоји од свих ниски облика vw где је v ниска језика L₁ док је w ниска језика L₂.
• Пресек L₁ ∩ L₂ језика L₁ и L₂ се састоји од свих ниски које се налазе у оба језика.
• Комплемент ¬L језика у односу на дату азбуку се састоји од свих ниски над том азбуком које нису у језику L.
• Клинијева звезда: језик који се састоји од свих речи које су конкатенација нула или више речи почетног језика;
• Обрат:
  • Нека је e празна ниска. Тада је e^R = e, и
  • за сваку непразну реч w = x₁…x_n над неком азбуком, нека је w^R = x_n…x₁,
  • тада за формални језик L,  w ∈ L}.
• Хомоморфизам ниски.

Такве операције над нискама се користе за изучавање својстава затворења класа језика. Класа језика је затворена у односу на одређену операцију, када ако се операција примени на језике те класе, увек даје језике који припадају истој тој класи. На пример, контекстно-слободни језици су затворени у односу на унију, конкатенацију и пресек са регуларним језицима, али нису затворени за пресек или комплемент.

Својства затворења фамилија језика ($L_{1}$ оператор $L_{2}$ где и $L_{1}$ и $L_{2}$ припадају фамилији језика назначеној на врху колоне). Дато по Хопкрофту и Улману.

Операција		регуларан	ДКСЈ	КСЈ	КОЈ	рекурзиван	р. п.
унија	$\{w|w\in L_{1}\lor w\in L_{2}\}$	Да	Не	Да	Да	Да	Да
пресек	$\{w|w\in L_{1}\land w\in L_{2}\}$	Да	Не	Не	Да	Да	Да
комплемент	$\{w|w\not \in L_{1}\}$	Да	Да	Не	Да	Да	Не
конкатенација	$L_{1}\cdot L_{2}=\{w\cdot z|w\in L_{1}\land z\in L_{2}\}$	Да	Не	Да	Да	Да	Да
Клинијева звезда	$L_{1}^{*}=\{\epsilon \}\cup \{w\cdot z|w\in L_{1}\land z\in L_{1}^{*}\}$	Да	Не	Да	Да	Да	Да
хомоморфизам		Да	Не	Да	Не	Не	Да
e-слободан хомоморфизам		Да	Не	Да	Да	Да	Да
супституција		Да	Не	Да	Да	Не	Да
инверзни хомоморфизам		Да	Да	Да	Да	Да	Да
обрат	$\{w^{R}|w\in L\}$	Да	Не	Да	Да	Да	Да
пресек са регуларним језиком	$\{w|w\in L_{1}\land w\in R,R{\text{ regular}}\}$	Да	Да	Да	Да	Да	Да

Види још

• Азбука (рачунарство)
• Формална граматика
• Формални метод
• Формална наука
• Формални систем
• Математичка нотација
• Програмски језик

Референце

• 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..

Спољашње везе

• Азбука на сајту PlanetMath
• Језик на сајту PlanetMath
• Универзитет Мериленда, Дефиниције формалних језика
• Џејмс Пауер, Белешке о теорији формалних језика и парсирању Архивирано на сајту Wayback Machine (21. новембар 2007), 29. новембар 2002.
• Нацрти неких поглавља из Уџбеника теорије формалних језика, томови 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