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

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