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;
Odkazy
Literatura
Související články jazyk (lingvistika) formální gramatika redukovaná gramatika volný monoid regulární výraz
Externí odkazy
Kategorie:Formální jazyky Kategorie:Formální vědy