NANJING UNIVERSITY Context-Free Grammars Formalism Derivations Backus-Naur Form Left-and Rightmost Derivations .1
Formalism Derivations Backus-Naur Form Left- and Rightmost Derivations Context-Free Grammars 1
效绵鼎 W-WR Not a regular language. ■1 Think about On10n,Pumping Lemma
◼ w=wR ◼ Not a regular language. ◼ Think about 0n10n , Pumping Lemma
效绵鼎 Informal Comments A context-free grammar is a notation for describing languages. ■ It is more powerful than finite automata or RE's, but still cannot define all possible languages. Useful for nested structures,e.g.,parentheses in programming languages 4
Informal Comments ◼ A context-free grammar is a notation for describing languages. ◼ It is more powerful than finite automata or RE’s, but still cannot define all possible languages. ◼ Useful for nested structures, e.g., parentheses in programming languages. 4
效绵县 Informal Comments -(2) Basic idea is to use "variables"to stand for sets of strings (i.e.,languages) These variables are defined recursively,in terms of one another. Recursive rules "productions")involve only concatenation. Alternative rules for a variable allow union. .5
Informal Comments – (2) ◼ Basic idea is to use “variables” to stand for sets of strings (i.e., languages). ◼ These variables are defined recursively, in terms of one another. ◼ Recursive rules (“productions”) involve only concatenation. ◼ Alternative rules for a variable allow union. 5
赖绵县 Example:CFG for on1n n1 Productions: S->01 S->0S1 Basis:01 is in the language. Induction:if w is in the language,then so is 0w1. .6
Example: CFG for { 0n1 n | n > 1} ◼ Productions: S -> 01 S -> 0S1 ◼ Basis: 01 is in the language. ◼ Induction: if w is in the language, then so is 0w1. 6