效绵鼎 Iterated Derivation =>*means“zero or more derivation steps.” Basis:a=>*a for any string a. Induction:if a=>*B and B=>y,then a=>*y. .12
Iterated Derivation ◼ =>* means “zero or more derivation steps.” ◼ Basis: =>* for any string . ◼ Induction: if =>* and => , then =>* . 12
效绵鼎 Example:Iterated Derivation S->01;S->0S1. ■S=>0S1=>00S11=>000111. Thus S=>*S;S=>*0S1;S=>*00S11;S=>* 000111. .13
Example: Iterated Derivation ◼ S -> 01; S -> 0S1. ◼ S => 0S1 => 00S11 => 000111. ◼ Thus S =>* S; S =>* 0S1; S =>* 00S11; S =>* 000111. 13
效绵鼎 Sentential Forms Any string of variables and/or terminals derived from the start symbol is called a sentential form. Formally,o is a sentential form iff S=>*0, .14
Sentential Forms ◼ Any string of variables and/or terminals derived from the start symbol is called a sentential form. ◼ Formally, is a sentential form iff S =>* . 14
效绵鼎 Language of a Grammar If G is a CFG,then L(G),the language ofG,is {wl S=>*W}. Example:G has productions S->E and S->0S1. L(G={0n1n|n≥0}. .15
Language of a Grammar ◼ If G is a CFG, then L(G), the language of G, is {w | S =>* w}. ◼ Example: G has productions S -> ε and S -> 0S1. ◼ L(G) = {0n1 n | n > 0}. 15
效绵鼎 Context-Free Languages A language that is defined by some CFG is called a context-free language. There are CFL's that are not regular languages, such as the example just given. But not all languages are CFL's. Intuitively:CFL's can count two things,not three. ,16
Context-Free Languages ◼ A language that is defined by some CFG is called a context-free language. ◼ There are CFL’s that are not regular languages, such as the example just given. ◼ But not all languages are CFL’s. ◼ Intuitively: CFL’s can count two things, not three. 16