南京大学：《形式语言与自动机 Formal Languages and Automata》课程教学资源（PPT课件讲稿）Context Free Grammar

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