Název:
Semilineární množiny
Překlad názvu:
Semilinear sets
Autoři:
Bouška, David ; Holub, Štěpán (vedoucí práce) ; Žemlička, Jan (oponent) Typ dokumentu: Bakalářské práce
Rok:
2016
Jazyk:
cze
Abstrakt: [cze][eng] V této práci se zabýváme částí matematické stránky teorie bezkontextových ja- zyků - semilineárními množinami. Předvedeme důkazy uzavřenosti semilineárních množin na průnik a rozdíl, a to v matematicky stravitelnější a případně jednodušší podobě, než v jaké se vyskytují jakožto doplňující výsledek v použité literatuře. Dále vysvětlíme pojem bezkontextové gramatiky a jazyka a bez důkazu uvedeme jeden z výsledků, které uvádějí semilineární množiny do souvislosti s bezkontex- tovými jazyky. 1In this thesis we examine a part of the mathematical side of the theory of context free languages, namely semilinear sets. We prove that the semilinear sets are closed under set intersection and difference in a mathematically better digestible and possibly easier way than how it is presented as a non-central result in the referenced literature. Then we introduce the notion of a context-free language and present a result that relates semilinear sets and context-free languages without a proof. 1
Klíčová slova:
semilineární množina lineární množina bezkontextová gramatika bezkontextový jazyk; semilinear set linear set context-free grammar context-free language