Formal Languages and Automata Theory

Géza Horváth, Benedek Nagy


Tartalom

Formal Languages and Automata Theory
Introduction
1. Elements of Formal Languages
1.1. Basic Terms
1.2. Formal Systems
1.3. Generative Grammars
1.4. Chomsky Hierarchy
2. Regular Languages and Finite Automata
2.1. Regular Grammars
2.2. Regular Expressions
2.3. Finite Automata as Language Recognizers
2.3.1. Synthesis and Analysis of Finite Automata
2.3.2. The Word Problem
2.4. Properties of Regular Languages
2.4.1. Closure Properties
2.4.2. Myhill-Nerode theorem
2.5. Finite Transducers
2.5.1. Mealy Automata
2.5.2. Moore Automata
2.5.3. Automata Mappings
3. Linear Languages
3.1. Linear Grammars
3.2. One-Turn Pushdown Automata
3.3. Closure Properties
4. Context-free Languages
4.1. Notation Techniques for Programming Languages
4.1.1. Backus-Naur Form
4.1.2. Syntax Diagram
4.2. Chomsky Normal Form
4.3. Pumping Lemma for Context-free Languages
4.4. Closure Properties
4.5. Parsing
4.5.1. The CYK Algorithm
4.5.2. The Earley Algorithm
4.6. Pushdown Automata
4.6.1. Acceptance by Empty Stack
4.6.2. Equivalence of PDAs and Context-free Grammars
4.6.3. Deterministic PDA
4.6.4. One-turn Pushdown Automata
5. Context-Sensitive Languages
5.1. Context-Sensitive and Monotone Grammars
5.1.1. Normal Forms
5.2. Linear Bounded automata
5.3. Properties of Context-Sensitive Languages
5.3.1. Closure Properties
5.3.2. About the Word Problem
6. Recursively Enumerable Languages and Turing Machines
6.1. Recursive and Recursively Enumerable Languages
6.1.1. Closure Properties
6.1.2. Normal Forms
6.2. Turing Machine, the Universal Language Acceptor
6.2.1. Equivalent Definitions
6.3. Turing Machine, the Universal Computing Device
6.4. Linear Bounded Automata
7. Literature

Az ábrák listája

2.1. In derivations the rules with long right hand side are replaced by chains of shorter rules, resulting binary derivation trees in the new grammar.
2.2. The graph of the automaton of Example 21.
2.3. The graph of the automaton of Exercise 19.
2.4. The graph of the automaton of Exercise 22.
2.5. The graph of the automaton of Exercise 25.
2.6. The graph of the automaton of Example 26.
2.7. The equivalence of the three types of descriptions (type-3 grammars, regular expressions and finite automata) of the regular languages.
2.8. The graph of the automaton of Exercise 31.
2.9. The graph of the automaton of Exercise 32.
2.10. The graph of the automaton of Exercise 37.
2.11. The graph of the Mealy automaton of Example 30.
2.12. The graph of the Mealy automaton of Exercise 42.
2.13. The graph of the Mealy automaton of Exercise 33.
2.14. The graph of the Mealy automaton of Exercise 46.
3.1. In derivations the rules with long right hand side (left) are replaced by chains of shorter rules in two steps, causing a binary derivation tree in the resulting grammar (right).
4.1. Syntax diagram.
4.2. The triangular matrix M for the CYK algorithm.
4.3. The triangular matrix M for the CYK algorithm of the Example 45.
4.4. The triangular matrix M for the Earley algorithm.
4.5. The triangular matrix M for the Earley algorithm of the Example 46.
4.6. The graphical notation for the Example 47.
4.7. The graphical notation for the Example 48.
4.8. The graphical notation for the Example 49.
4.9. The graphical notation for the Example 50.
5.1. In derivations the rules with long right hand side are replaced by chains of shorter rules.
6.1. The graphical notation for the Example 58.

A táblázatok listája

4.1. Operations of the BNF metasyntax.