Formala lingvo
Ne konfuzu kun formala maniero de parolado/skribado
En matematiko oni konsideras formalajn lingvojn kun skriba reprezentaĵo. Alivorte, formala lingvo estas aro de finlongaj propozicioj (aŭ vortoj) konsistantaj el literoj (simboloj) de finkvanta alfabeto. Plej ofte oni uzas formalajn lingvojn en programado, matematika lingvistiko, teorio de aŭtomatoj, teorio de komputebleco, teorio de algoritmoj. Matematika teorio, kiu priskribas tiajn objektojn, nomiĝas Teorio de formalaj gramatikoj.
Kutime formala lingvo (en tiu ĉi artikolo ni nomos ĝin simple "lingvo") enhavas nefinitan kvanton de propozicioj. Klare, ke tiaj nefinitaj lingvoj povas esti difinitaj nur per iu matematika konstruaĵo.
En teorio ofte gravas, ĉu la lingvo enhavas malplenan propozicion (signatan kiel e, ε aŭ Λ).
Ekzemploj
Oni signas la lingvojn kutime per litero L (eble kun indeksoj).
- 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 sintakse ĝustaj programoj en certa lingvo de programado.
Manieroj de difino
Formala lingvo povas esti difinita en diversaj manieroj, ekzemple:
- Per tranombrado; tamen tiel oni povas difini nur lingvojn kun finita kvanto de propozicioj.
- Per iu formala gramatiko.
- Per iu regula esprimo.
- Per iu fina aŭtomato.
- Per formo de Backus-Naur.
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).