Original title: Obecné gramatiky: Normální formy a jejich aplikace
Translated title: General Grammars: Normal Forms with Applications
Authors: Klobučníková, Dominika ; Krčmář, Radim (referee) ; Meduna, Alexandr (advisor)
Document type: Bachelor's theses
Year: 2017
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
Táto práca sa zaoberá problematikou obecných gramatík, normálnych foriem a ich aplikácií. Zameriava sa na kontextové gramatiky ako ich špeciálne prípady. Na základe analýzy tejto množiny bol navrhnutý algoritmus využívajúci princípy Cocke-Younger-Kasami algoritmu za účelom rozhodnutia, či zadaný reťazec je vetou jazyka definovaného kontextovou gramatikou. Výsledná aplikácia implementujúca toto riešenie je navrhnutá pre prácu s kontextovými gramatikami v Penttonenovej normálnej forme. This thesis deals with the topic of unrestricted grammars, normal forms, and their applications. It focuses on context-sensitive grammars as their special cases. Based on the analysis of the set, an algorithm was designed using the principles of the Cocke-Younger-Kasami algorithm to make a decision of whether an input string is a sentence of a context-sensitivegrammar. The final application, which implements this algorithm, works with context-sensitive grammars in the Penttonen normal form.
Keywords: CKY; Cocke-Younger-Kasami; CYK; formal languages; grammars; Kuroda; normal forms; Penttonen; syntax analysis; CKY; Cocke-Younger-Kasami; CYK; formálne jazyky; gramatiky; Kuroda; normálne formy; Penttonen; syntaktická analýza

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/69729

Permalink: http://www.nusl.cz/ntk/nusl-364034


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Bachelor's theses