Formální jazyk

Technology

12 hours ago

Author

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 \left \{ a , b \right \}, řetězcem nad touto abecedou je například ababba. Příkladem jazyka může být množina všech řetězců nad touto abecedou, které obsahují stejný počet symbolů a jako b.

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čí e, \epsilon (epsilon) nebo λ.

Pokud označíme abecedu symbolem \Sigma, pak zápis \Sigma^{*} označuje množinu všech řetězců nad touto abecedou, včetně prázdného řetězce. Jazyk L nad danou abecedou \Sigma je pak nějaká podmnožina \Sigma^{*}. +more 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 {a, b} * množina \left \{ a^{n}\right\}, n je přirozené číslo a a^{n} 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 ř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;