效绵鼎 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