načítání...
nákupní košík
Košík

je prázdný
a
b

Kniha: Automaty a gramatiky - Sbírka řešených příkladů - Eliška Šestáková

Automaty a gramatiky - Sbírka řešených příkladů
-7%
sleva

Kniha: Automaty a gramatiky - Sbírka řešených příkladů
Autor:

Učební text je koncipován především jako sbírka řešených příkladů z teorie formálních jazyků, gramatik a automatů. U jednotlivých úloh jsou spolu s řešením vždy uvedeny i ... (celý popis)
Titul doručujeme za 3 pracovní dny
Vaše cena s DPH:  235 Kč 219
+
-
rozbalKdy zboží dostanu
7,3
bo za nákup
rozbalVýhodné poštovné: 39Kč
rozbalOsobní odběr zdarma

hodnoceni - 0%hodnoceni - 0%hodnoceni - 0%hodnoceni - 0%hodnoceni - 0%   celkové hodnocení
0 hodnocení + 0 recenzí

Specifikace
Nakladatelství: » ČVUT Praha
Médium / forma: Tištěná kniha
Rok vydání: 2017
Počet stran: 194
Rozměr: 210x297
Úprava: ilustrace
Vydání: 1. vydání
Skupina třídění: Kombinatorika. Teorie grafů. Matematická statistika. Operační výzkum. Matematické modelování
Učební osnovy. Vyučovací předměty. Učebnice
Jazyk: česky
Datum vydání: 27.09.2017
ISBN: 978-80-01-06306-4
EAN: 9788001063064
Ukázka: » zobrazit ukázku
Popis

Učební text je koncipován především jako sbírka řešených příkladů z teorie formálních jazyků, gramatik a automatů. U jednotlivých úloh jsou spolu s řešením vždy uvedeny i hlavní myšlenky, které k danému řešení vedly. Autorka též vysvětluje použité formalismy a algoritmy a poukazuje na časté chyby studentů.

(sbírka řešených příkladů)

Předmětná hesla
Formální jazyky -- Úlohy
regulární jazyky -- úlohy
bezkontextové jazyky -- úlohy
Konečný automat -- Úlohy
Kniha je zařazena v kategoriích
Eliška Šestáková - další tituly autora:
Automata and Grammars - A Collection of exercises and Solutions Automata and Grammars
 
Recenze a komentáře k titulu
Zatím žádné recenze.


Ukázka / obsah
Přepis ukázky

Obsah

1 Formální jazyky, gramatiky a jejich klasifikace 7

1.1 Formálni ja z y k y ....................................................................................................................... 7

1.2 Klasifikace formálních ja z y k ů ................................................................................................ 8

1.3 Gramatiky a jej ich k lasifikace................................................................................................ 10

2 Regulární jazyky 15

2.1 Regulární g r a m a tik y .............................................................................................................. 15

2.1.1 Návrh regulární gramatiky pro zadaný j a z y k ............................................................ 15

2.2 Konečné a u to m a ty ................................................................................................................. 22

2.2.1 Návrh konečného autom atu pro zadaný ja z y k ......................................................... 25

2.2.2 Odstranění nedosažitelných a zbytečných s ta v ů...................................................... 36

2.2.3 Odstranění г - p ř e c h o d ů .............................................................................................. 39

2.2.4 Odstranění více počátečních s ta v ů ............................................................................. 42

2.2.5 D eterm inizace.............................................................................................................. 44

2.2.6 Minimalizace deterministického konečného autom atu ........................................ 48

2.2.7 Skládání a u to m a tů ...................................................................................................... 54

2.3 Regulární výrazy....................................................................................................................... 61

2.3.1 Návrh regulárního výrazu pro zadaný jazyk ............................................................ 61

2.3.2 Úprava regulárního v ý r a z u ........................................................................................ 63

2.3.3 Regulární ro v n ic e ......................................................................................................... 64

2.3.4 Soustava regulárních ro v n ic........................................................................................ 64

2.3.5 Derivace regulárních výrazů ..................................................................................... 68

2.4 Převody mezi regulárními výrazy, konečnými automaty a regulárními gramatikami . . . 69

2.4.1 Regulární gramatika — konečný a u to m a t................................................................. 70

2.4.2 Konečný autom at — regulární g ram atik a.................................................................. 71

2.4.3 Regulární výraz —* konečný autom at ....................................................................... 73

2.4.4 Konečný autom at — regulární v ý ra z .......................................................................... 80

2.4.5 Regulární gramatika — regulární v ý r a z.................................................................... 85

2.4.6 Regulární výraz — regulární g ra m a tik a.................................................................... 89

2.5 Pumping lemma .................................................................................................................... 91

2.5.1 Použití v důkazu o neregularitě jazyka....................................................................... 92

2.5.2 Určení konstanty pum ping lemmatu pro zadaný ja z y k ........................................... 110

2.6 Myhill-Nerodova věta ............................................................................................................ 113

2.6.1 Použití v důkazu o neregularitě jazyka....................................................................... 113

2.6.2 Použití v důkazu o regularitě ja z y k a .......................................................................... 120

2.7 Uzáverové v la s tn o s ti.............................................................................................................. 121

2.7.1 Použití v důkazu o neregularitě jazyka...................................................................... 121

5


3 Bezkontextové jazyky

3.1 Bezkontextové g r a m a tik y .....................................................................................

3.1.1 Derivační s tr o m ...........................................................................................

3.1.2 Jednoznačnost a v íc e z n a č n o s t..................................................................

3.1.3 Návrh bezkontextové gramatiky pro zadaný jazy k....................................

3.1.4 Odstranění ^ -p ra v id e l...............................................................................

3.1.5 Odstranění jednoduchých p r a v id e l..........................................................

3.1.6 Odstranění zbytečných sy m b o lů ...............................................................

3.1.7 Odstranění levé r e k u r z e .............................................................................

3.1.8 Normální tvar podle Chom ského...............................................................

3.2 Algoritmus Cocke-Younger-Kasami....................................................................

3.3 Zásobníkové a u to m a ty ..........................................................................................

3.3.1 Návrh zásobníkového automatu pro zadaný jazyk .................................

3.3.2 Syntaktická analýza (bezkontextová gramatika — zásobníkový automat)

123

. 123

. 123

. 124

. 125

. 135

. 137

. 139

. 142

. 145

. 148

. 152

. 156

. 167

4 Formální překlady

4.1 Překladové gramatiky ................................................................................

4.1.1 Návrh regulární překladové gramatiky pro zadaný překlad ....

4.1.2 Návrh bezkontextové překladové gramatiky pro zadaný překlad .

4.2 Překladové a u to m a ty ..................................................................................

4.2.1 Návrh konečného překladového automatu pro zadaný překlad . .

4.2.2 Návrh zásobníkového překladového automatu pro zadaný překlad

171

. 171

. 172

. 173

. 176

. 177

. 178

5

Kontextové jazyky

5.1 Kontextové g ra m a tik y ...............................................

5.1.1 Návrh gramatiky pro zadaný kontextový jazyk

5.2 Lineárně omezené Turingovy s t r o j e .........................

5.2.1 Návrh lineárně omezeného Turingova stroje .

183

183

183

185

187

6 Rekurzivně spočetné jazyky

6.1 Neomezené g ram atik y ...............................................

6.1.1 Návrh neomezené gramatiky pro zadaný jazyk

6.2 Turingovy s tr o je ..........................................................

6.2.1 Návrh Turingova stroje pro zadaný jazyk . . .

6.2.2 Třídy složitosti P a N P ....................................

189

190

190

190

191

191

6




       
Knihkupectví Knihy.ABZ.cz - online prodej | ABZ Knihy, a.s.
ABZ knihy, a.s.
 
 
 

Knihy.ABZ.cz - knihkupectví online -  © 2004-2019 - ABZ ABZ knihy, a.s. TOPlist