Original title:
Semilineární množiny
Translated title:
Semilinear sets
Authors:
Bouška, David ; Holub, Štěpán (advisor) ; Žemlička, Jan (referee) Document type: Bachelor's theses
Year:
2016
Language:
cze Abstract:
[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
Keywords:
semilinear set linear set context-free grammar context-free language; semilineární množina lineární množina bezkontextová gramatika bezkontextový jazyk
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/84559