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
效绵鼎 CFG Formalism Terminals symbols of the alphabet of the language being defined Variables nonterminals a finite set of other symbols,each of which represents a language. Start symbol the variable whose language is the one being defined 7
CFG Formalism ◼ Terminals = symbols of the alphabet of the language being defined. ◼ Variables = nonterminals = a finite set of other symbols, each of which represents a language. ◼ Start symbol = the variable whose language is the one being defined. 7
效绵鼎 Productions A production has the form variable (head)->string of variables and terminals (body) Convention: o A,B.C....and also S are variables. 0 a,b,c,...are terminals. ...X,Y,Z are either terminals or variables. ...w,x,y,z are strings of terminals only. 0 a,B,y,...are strings of terminals and/or variables 8
Productions ◼ A production has the form variable (head) -> string of variables and terminals (body). ◼ Convention: A, B, C,… and also S are variables. a, b, c,… are terminals. …, X, Y, Z are either terminals or variables. …, w, x, y, z are strings of terminals only. , , ,… are strings of terminals and/or variables. 8
效绵鼎 Example:Formal CFG Here is a formal CFG for on1nn1 Terminals {0,1). Variables ={S}. ■ Start symbol S. ■ Productions S->01 S->0S1 9
Example: Formal CFG ◼ Here is a formal CFG for { 0n1 n | n > 1}. ◼ Terminals = {0, 1}. ◼ Variables = {S}. ◼ Start symbol = S. ◼ Productions = S -> 01 S -> 0S1 9
效绵鼎 Derivations -Intuition We derive strings in the language of a CFG by starting with the start symbol,and repeatedly replacing some variable A by the body of one of its productions. That is,the "productions for A"are those that have head A. .10
Derivations – Intuition ◼ We derive strings in the language of a CFG by starting with the start symbol, and repeatedly replacing some variable A by the body of one of its productions. That is, the “productions for A” are those that have head A. 10
效绵县 Derivations -Formalism We say aAβ=>oyβifA->y is a production. Example:S->01;S->0S1. Q>0>0O1. .11
Derivations – Formalism ◼ We say A => if A -> is a production. ◼ Example: S -> 01; S -> 0S1. ◼ S => 0S1 => 00S11 => 000111. 11