Formala lingvo

El Vikipedio, la libera enciklopedio
Salti al navigilo Salti al serĉilo

Ne konfuzu kun formala maniero de parolado/skribado

Vastasence formala lingvo estas lingvo kies sintakso kaj semantiko havas rigoran matematikan difinon.[1] Grava ekzemplo estas la programlingvoj kaj deversaj logikaj kalkuloj. La nocio apartenas al semiotiko, matematiko, komputado, lingvoscienco.

Formalaj difinoj semantikaj estas diversaj kaj malfacilaj, dum por la priskriboj sintaksaj ekzistas tute taŭgaj kaj ĝenerale akcepitaj rimedoj teoriaj kaj praktikaj. Krome, la idealo matematika estas redukti semantikon al sintaktso (rezoni laŭforme, komkludi pri vereco surbaze de sintaksa ĝusteco). Tio plene prosperis pri la propozicia kalkulo; tio maleblas pri formalaj sistemoj pli malsimplaj.

Ĉi-sube formala lingvo estos traktata en la malvasta signifo sintakse formala lingvo. Ĝi precipe aktualas por teorio de aŭtomatoj, teorio de komputebleco, teorio de algoritmoj. Ĝi estas studata en la Teorio de formalaj gramatikoj.

Difino[redakti | redakti fonton]

Alfabeto (en la kadro de la teorio pri formalaj lingvoj) estas ajna aro elektita por tiu rolo en koncerna fortmala lingvo. Interalie ĝi povas esti la komunlingva alfabeto de Esperanto; aŭ Askio, aŭ Unikodo. Kutime oni konsideras alfabetojn finiajn, kvankam ekzistas teorioj kiuj ebligas uzon de alfabetoj malfiniaj. Alfabeton oni kutime signas per Σ (de «Simbolaro»). Anojn de la alfabeto oni nomas literoj.

Vorto super tia alfabeto estas ajna opo (finia vico, ĉeno) da ties anoj (en la praktikaj aplikoj «vorto» normale respondas al propozicio, kompleta frazo). La aro da ĉiuj vortoj super Σ oni kutime signas per . Vortlongo estas la nombro de literpozicioj en la koncerna vorto. En ĉiu ekzistas precize unu vorto kies longo estas 0, la vakuo[1] (= «malplena vorto», «malplenaĵo»). Vakuon oni kutime signas per Λ (germane leer, aŭ renversita V de la esperanta Vakuo), aŭ per ε (angle empty).

Formala lingvo L super la alfabeto Σ estas subaro de : .

En teorio de sintaksa analizo ofte gravas, ĉu la lingvo enhavas la vakuon (t.e. ĉu ).

En kelkaj aplikoj oni ŝovas la metaforojn kaj preferas nomi la alfabeton vortaro kaj la vortojn propozicioj.

Ekzemploj[redakti | redakti fonton]

  • Estu la alfabeto {a, b} kaj enhavu la lingvo L ĉiujn vortojn el tiu ĉi alfabeto. Tiam ekzemple ankaŭ la vorto ababbab apartenas al L.
  • Estu la alfabeto {a} (alivorte unulitera alfabeto). La lingvo L konsistas el vortoj kun nepara kvanto de literoj a. Tiam (ekzemple) la vorto aaa apartenas al lingvo, la vorto aaaa ne.
  • aro de la sintakse ĝustaj programoj en certa programlingvo.

Manieroj de difino[redakti | redakti fonton]

Formala lingvo povas esti difinita en diversaj manieroj, ekzemple:

Literaturo[redakti | redakti fonton]

  • J.E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation Second Edition. Addison-Wesley (2001).
  • J.E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Enkonduko en teorio de aŭtomatoj, lingvoj kaj komputado Dua eldono. Addison-Wesley (2001) (en la angla).
  • Серебряков В.А., Галочкин М.П., Гончар Д.Р., Фуругян М.Г. Теория и реализация языков программирования //М.: МЗ-Пресс, 2006 г., 2-е изд. "Serebrjakov V.A., Galoĉkin M.P., Gonĉar D.R., Furugjan M.G." Teorio kaj realizado de lingvoj de programado //Moskvo: МЗ-Press, 2006 ., 2a eldono. ISBN 94073-094-9 (en la rusa).

Piednotoj[redakti | redakti fonton]

  1. 1,0 1,1 Komputada Leksikono.