Transcription of Chapter 3 Context-Free Grammars, Context-Free Languages ...
{{id}} {{{paragraph}}}
Example: barber
Chapter 3 Context-Free Grammars, Context-Free Languages ...
Chapter 3 Context-Free Grammars, Context-Free Languages , Parse Treesand Ogden s Context-Free GrammarsA Context-Free grammar basically consists of a finite set of grammar rules. In order to definegrammar rules, we assume that we have two kinds of symbols: the terminals, which are thesymbols of the alphabet underlying the Languages under consideration, and the nonterminals,which behave like variables ranging over strings of terminals. A rule is of the formA ,whereAis a single nonterminal, and the right-hand side is a string of terminal and/ornonterminal symbols. As usual, first we need to define what the object is (a context-freegrammar), and then we need to explain how it is used. Unlike automata, grammars are usedtogeneratestrings, rather than recognize grammar (for short, CFG)is a quadrupleG=(V, ,P,S),where Vis a finite set of symbols called thevocabulary (or set of grammar symbols); Vis the set ofterminal symbols (for short, terminals); S (V ) is a designated symbol called thestart symbol; P (V ) V is a finite set ofproductions (or rewrite rules, or rules).
38 CHAPTER 3. CONTEXT-FREE GRAMMARS AND LANGUAGES Lemma 3.2.4 Let G =(V,Σ,P,S) be a context-free grammar. For every w ∈ Σ∗,for every derivation S =+⇒ w, there is a leftmost derivation S =+⇒ lm w, and there is a rightmost derivation S =+⇒ rm w. Proof.Of course, we have to somehow use induction on derivations, but this is a little
Loading..
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: