Formální jazyk
Formální jazyk je v matematice, logice a informatice libovolná množina konečných řetězců (tj. řetězců konečné délky) nad určitou abecedou. Místo výrazu „řetězec“ se často používá výraz „slovo“ (zejména při lexikální analýze) nebo „věta“ (zejména při syntaktické analýze a analýze vět přirozeného jazyka). Přesná definice pojmu formální jazyk se může lišit 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 , řetězcem nad touto abecedou je například . Příkladem jazyka může být množina všech řetězců nad touto abecedou, které obsahují stejný počet symbolů jako .
Přestože abeceda je konečná množina a řetězce mají konečnou délku, jazyk konečný být nemusí, jelikož délka (stále konečných) řetězců nemusí být shora omezena.
Značení
Prázdný řetězec (tj. řetězec, který se skládá z nulového počtu znaků) se značí , (epsilon) nebo λ.
Pokud označíme abecedu symbolem , pak zápis označuje množinu všech řetězců nad touto abecedou, včetně prázdného řetězce. Jazyk nad danou abecedou je pak nějaká podmnožina . Hvězdičkou zapisovaná na místě horního indexu je operátor nazývaný Kleeneho hvězdička, který označuje zřetězení libovolného konečného počtu (včetně 0) prvků z množiny, na níž je aplikován.
Příklady formálních jazyků
Příklady formálních jazyků:
- množina všech řetězců nad abecedou
- množina , n je přirozené číslo a znamená, že se vyskytuje -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 řetězců, nad kterými daný Turingův stroj zastaví.
Formální jazyk může být definován různými způsoby, například:
- všechny řetězce generované nějakou formální gramatikou (viz Chomského hierarchie);
- všechny řetězce a vyhovující nějakému regulárnímu výrazu;
- všechny řetězce akceptované nějakým automatem, například Turingovým strojem nebo konečným automatem;