Formální jazyk

Z Wikipedie, otevřené encyklopedie

V matematice, logice a informatice se pojmem formální jazyk označuje množina konečných slov (tj. slov konečné délky) nad určitou abecedou. Místo pojmu slovo se někdy užívá výraz řetězec. Definice pojmu formální jazyk se může měnit podle toho, v jakém kontextu a v jakém vědním oboru jej používáme.

Příkladem abecedy může být , slovem nad touto abecedou je například ababba. Příkladem jazyka můžou být slova nad touto abecedou, která obsahují stejný počet symbolů a a b.

Prázdné slovo (tj. slovo, které se skládá z nulového počtu znaků) se značí e, ε nebo Λ. Ačkoli abeceda je konečná množina a každé slovo je konečná množina, jazyk konečný být nemusí, jelikož délka slov nemusí být shora omezena.

Abeceda je obvykle značena symbolem Σ. Zápis Σ ^* pak označuje jazyk, obsahující všechna slova nad danou abecedou, včetně prázdného slova. Každý jazyk Lnad určitou abecedou Σ je podmnožinou jazyka Σ ^* .

Příklady formálních jazyků:

• množina všech slov nad abecedou a,b
• množina , n je přirozené číslo a aⁿ znamená, že a se vyskytuje n-krát za sebou.
• konečné jazyky jako například a,aa,bba
• množina všech programů v daném programovacím jazyce
• množina všech slov, nad kterými daný Turingův stroj zastaví.

Formální jazyk může být definován různými způsoby, například :

• slova generovaná nějakou formální gramatikou (viz Chomského hierarchie);
• slova vyhovující nějakému regulárnímu výrazu;
• slova akceptovaná nějakým automatem, například Turingovým strojem nebo konečným automatem;