# Gjuha formale

Struktura e fjalisë angleze të mirëformuar sintaksorisht, edhe pse e pakuptimtë, *"Colorless green ideas sleep furiously"* (shembull historik nga Chomsky 1957).
Në logjikë, matematikë, shkenca kompjuterike dhe gjuhësi, një **gjuhë formale** përbëhet nga fjalë, shkronjat e të cilave janë marrë nga një alfabet dhe janë të mirëformuara sipas një grupi të caktuar rregullash.

Alfabeti i një gjuhe formale përbëhet nga simbole, shkronja ose shenja që bashkohen në vargjet e gjuhës. Çdo varg i lidhur nga simbolet e këtij alfabeti quhet fjalë, dhe fjalët që i përkasin një gjuhe të caktuar formale quhen ndonjëherë *fjalë të formuara mirë* ose *formula të formuara mirë*. Një gjuhë formale shpesh përkufizohet me anë të një gramatike formale, siç është gramatika e rregullt ose gramatika pa kontekst, e cila përbëhet nga rregullat e formimit të saj.

Në shkencën kompjuterike, gjuhët formale përdoren ndër të tjera si bazë për përcaktimin e gramatikës së gjuhëve të programimit dhe versioneve të formalizuara të nëngrupeve të gjuhëve natyrore, në të cilat fjalët e gjuhës përfaqësojnë koncepte që lidhen me kuptime ose semantikë të veçantë. Në teorinë e kompleksitetit llogaritës, problemet e vendimit përcaktohen në mënyrë tipike si gjuhë formale, dhe klasat e kompleksitetit përcaktohen si grupe të gjuhëve formale që mund të analizohen nga makinat me fuqi të kufizuar llogaritëse. Në logjikë dhe themelet e matematikës, gjuhët formale përdoren për të përfaqësuar sintaksën e sistemeve aksiomatike, dhe formalizmi matematik është filozofia që e gjithë matematika mund të reduktohet në manipulimin sintaksor të gjuhëve formale në këtë mënyrë.

Fusha e **teorisë së gjuhës formale** studion kryesisht aspektet thjesht sintaksore të gjuhëve të tilla - domethënë modelet e tyre të brendshme strukturore. Teoria e gjuhës formale doli nga gjuhësia, si një mënyrë për t'i kuptuar rregullsitë sintaksore të gjuhëve natyrore.

## Fjalët mbi një alfabet

Një **alfabet**, në kontekstin e gjuhëve formale, mund të jetë çdo grup, megjithëse shpesh ka kuptim të përdoret një alfabet në kuptimin e zakonshëm të fjalës, ose më përgjithësisht çdo kodim i caktuar i karaktereve, si ASCII ose Unicode. Elementet e një alfabeti quhen **shkronjat** e tij. Një alfabet mund të përmbajë një numër të pafund elementesh; megjithatë, shumica e përkufizimeve në teorinë e gjuhës formale specifikojnë alfabete me një numër të kufizuar elementesh dhe shumica e rezultateve zbatohen vetëm për to.

Një **fjalë** mbi një alfabet mund të jetë çdo sekuencë e fundme (dmth. varg) shkronjash. Bashkësia e të gjitha fjalëve mbi një alfabet Σ zakonisht shënohet me Σ\* (duke përdorur yllin Kleene). Gjatësia e një fjale është numri i shkronjave nga të cilat ajo përbëhet. Për çdo alfabet, ekziston vetëm një fjalë me gjatësi 0, *fjala boshe*, e cila shpesh shënohet me e, ε, λ ose edhe Λ. Me anë të bashkimit mund të kombinohen dy fjalë për të formuar një fjalë të re, gjatësia e së cilës është shuma e gjatësive të fjalëve origjinale. Rezultati i lidhjes së një fjale me fjalën boshe është fjala origjinale.

## Shiko edhe

* Korniza gramatikore

## Referime

## Bibliografia

* Hopcroft, John E.; Ullman, Jeffrey D. (1979). *Introduction to Automata Theory, Languages, and Computation* (në anglisht). Reading, Massachusetts: Addison-Wesley Publishing. ISBN 81-7808-347-7.

## Lidhje të jashtme

* University of Maryland, Formal Language Definitions Arkivuar 16 shkurt 2008 tek Wayback Machine
* James Power, "Notes on Formal Language Theory and Parsing" Arkivuar 21 nëntor 2007 tek Wayback Machine Archived 21 November 2007 at the Wayback Machine, 29 November 2002.
* Draftet e disa kapitujve në "Handbook of Formal Language Theory", Vëll. 1–3, G. Rozenberg dhe A. Salomaa (eds.), Springer Verlag, (1997):
	+ Alexandru Mateescu and Arto Salomaa, "Preface" in Vol.1, pp. v–viii, dhe "Formal Languages: An Introduction and a Synopsis", Kapitulli 1 në Vëll. 1, pp.1–39
	+ Sheng Yu, "Regular Languages", Kapitulli 2 në Vëll. 1
	+ Jean-Michel Autebert, Jean Berstel, Luc Boasson, "Context-Free Languages and Push-Down Automata", Kapitulli 3 në Vëll. 1
	+ Christian Choffrut and Juhani Karhumäki, "Combinatorics of Words", Kapitulli 6 në Vëll. 1
	+ Tero Harju and Juhani Karhumäki, "Morphisms", Kapitulli 7 në Vëll. 1, pp. 439–510
	+ Jean-Eric Pin, "Syntactic semigroups", Kapitulli 10 in Vëll. 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