Formala lingvo

Vastasence **formala lingvo** estas lingvo kies sintakso kaj semantiko havas rigoran matematikan difinon. Gravaj ekzemploj estas la programlingvoj kaj diversaj 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 akceptitaj rimedoj teoriaj kaj praktikaj. Krome, la idealo matematika estas redukti semantikon al sintaktso (rezoni laŭforme, konkludi 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 
**Alfabeto** (en la kadro de la teorio pri formalaj lingvoj) estas ajna aro elektita por tiu rolo en koncerna formala 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»). Elementojn 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 \Sigma^*. **Vortlongo** estas la nombro de literpozicioj en la koncerna vorto. En ĉiu \Sigma^* ekzistas precize unu vorto kies longo estas 0, la **vakuo** (= «malplena vorto», «malplenaĵo»). Vakuon oni kutime signas per Λ (, aŭ renversita V de la esperanta Vakuo), aŭ per ε ().

**Formala lingvo** *L* super la alfabeto Σ estas subaro de \Sigma^*: L\subseteq\Sigma^*.

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

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

## Ekzemploj 
* La alfabeto estu {*a*, *b*}, kaj la lingvo *L* enhavu ĉiujn vortojn en tiu ĉi alfabeto. Tiam, ekzemple, ankaŭ la vorto *ababbab* apartenas al la lingvo *L*.
* La alfabeto estu {*a*} (alivorte, unulitera alfabeto), kaj la lingvo *L* konsistu el ĉiuj vortoj kun nepara nombro da literoj *a*. Tiam, ekzemple, la vorto *aaa* apartenas al la lingvo *L*, dum la vorto *aaaa* ne apartenas al ĝi.
* La aro de ĉiuj sintakse ĝustaj programoj en certa programlingvo.

## Manieroj de difino 
Formala lingvo povas esti difinita en diversaj manieroj, ekzemple:

* Per listigo; tamen tiel oni povas difini nur lingvojn kun finia kvanto de vortoj.
* Per iu formala gramatiko.
* Per iu regula esprimo.
* Per iu finia aŭtomato.
* Per EBNF.

## Literaturo 
* 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 
## Vidu ankaŭ 
* Natura lingvo

Kategorio:Matematiko
Kategorio:Teoria komputiko
Kategorio:Formalaj lingvoj