Poznámky
Osnova
Part VII.
Models for Context-Free Languages
Context-Free Grammar (CFG)
Context-Free Grammar: Definition
Convention
Derivation Step
Sequence of Derivation Steps 1/2
Sequence of Derivation Steps 2/2
Generated Language
Context-Free Language (CFL)
Rule Tree
Derivation Tree: Example
Leftmost Derivation
Leftmost Derivation: Example
Rightmost Derivation
Rightmost Derivation: Example
Derivations: Summary
Reduction of the Number of Derivations
Introduction to Ambiguity
Grammatical Ambiguity
Pushdown Automata (PDA)
Pushdown Automata: Definition
Notes on PDA Rules
Graphical Representation
Graphical Representation: Example
PDA Configuration
Move
Sequence of Moves 1/2
Sequence of Moves 2/2
Accepted Language: Three Types
PDA: Example
Three Types of Acceptance: Equivalence
Deterministic PDA (DPDA)
PDAs are Stronger than DPDAs
Extended PDA (EPDA)
Move in EPDA
EPDA: Example
Three Types of Acceptance: Equivalence
EPDAs and PDAs are Equivalent
EPDAs and PDAs as Parsing Models for CFGs
EPDAs as Models of Bottom-Up Parsers 1/2
EPDAs as Models of Bottom-Up Parsers 2/2
Algorithm: From CFG to EPDA
From CFG to EPDA: Example 1/2
From CFG to EPDA: Example 2/2
PDAs as Models of Top-Down Parsers 1/2
PDAs as Models of Top-Down Parsers 2/2
Algorithm: From CFG to PDA
From CFG to PDA: Example 1/2
From CFG to PDA: Example 2/2
Models for Context-free Languages