ࡱ> kmjk bjbj N}}<`lnnnnnnn& & & p!<!li`J"J"`"`"`" O O O] ] ] ]AJ]P^P_$a ?c`n OE O O O`gRnn`"`")##`gRgRgR On`"n`"]gR O]gRzgRXr@\nn\`">" 0g~`& Q\\9`0i`\cgRc\gRRXnnnnContext-Free Grammars Read K & S 3.1 Read Supplementary Materials: Context-Free Languages and Pushdown Automata: Context-Free Grammars Read Supplementary Materials: Context-Free Languages and Pushdown Automata: Designing Context-Free Grammars. Do Homework 11. Context-Free Grammars, Languages, and Pushdown Automata  Context-Free  Language  L  Context-Free Grammar Accepts  Pushdown Automaton Grammars Define Languages Think of grammars as either generators or acceptors. Example: L = {w ( {a, b}* : |w| is even} Regular Expression (aa ( ab ( ba ( bb)* Regular Grammar S ( ( S ( aT S ( bT T ( a T ( b T ( aS T ( bS Derivation (Generate) choose aa choose ab yields a a a b  S a T  a S  a T  b a a a b Parse (Accept) use corresponding FSM Derivation is Not Necessarily Unique Example: L = {w ( {a, b}* : there is at least one a} Regular Expression (a ( b)*a (a ( b)* choose a from (a ( b) choose a from (a ( b) choose a choose a choose a from (a ( b) choose a from (a ( b) Regular Grammar S ( a S ( bS S ( aS S ( aT T ( a T ( b T ( aT T ( bT  S S  a S a T  a S a T  a a More Powerful Grammars Regular grammars must always produce strings one character at a time, moving left to right. But sometimes it's more natural to describe generation more flexibly. Example 1: L = ab*a S ( aBa B ( ( B ( bB  vs. S ( aB B ( a B ( bB Example 2: L = anb*an S ( B S ( aSa B ( ( B ( bB Key distinction: Example 1 has no recursion on the nonregular rule. Context-Free Grammars Remove all restrictions on the form of the right hand sides. S ( abDeFGab Keep requirement for single non-terminal on left hand side. S ( but not ASB ( or aSb ( or ab ( Examples: balanced parentheses anbn S ( ( S ( a S b S ( SS S ( ( S ( (S) Context-Free Grammars A context-free grammar G is a quadruple (V, (, R, S), where: V is the rule alphabet, which contains nonterminals (symbols that are used in the grammar but that do not appear in strings in the language) and terminals, ( (the set of terminals) is a subset of V, R (the set of rules) is a finite subset of (V - () ( V*, S (the start symbol) is an element of V - (. x (G y is a binary relation where x, y ( V* such that x = (A( and y = ((( for some rule A(( in R. Any sequence of the form w0 (G w1 (G w2 (G . . . (G wn e.g., (S) ( (SS) ( ((S)S) is called a derivation in G. Each wi is called a sentinel form. The language generated by G is {w ( (* : S (G* w} A language L is context free if L = L(G) for some context-free grammar G. Example Derivations G = (W, (, R, S), where W = {S} ( (, ( = {a, b}, R = { S ( a, S ( aS, S ( aSb}  S S  a S a S b  a S b a S b  a S a S  a S b a S  a a Another Example - Unequal a's and b's L = {anbm : n ( m} G = (W, (, R, S), where W = {a, b, S, A, B}, ( = {a, b}, R = S ( A /* more a's than b's S ( B /* more b's than a's A ( a A ( aA A ( aAb B ( b B ( Bb B ( aBb English S ( NP VP NP ( the NP1 | NP1 NP1 ( ADJ NP1 | N ADJ ( big | youngest | oldest N ( boy | boys VP (V | V NP V ( run | runs the boys run big boys run the youngest boy runs the youngest oldest boy runs the boy run Who did you say Bill saw coming out of the hotel? Arithmetic Expressions The Language of Simple Arithmetic Expressions G = (V, (, R, E), where V = {+, *, id, T, F, E}, ( = {+, *, id}, R = { E ( id E ( E + E E ( E * E } E E  E + E E * E  id E * E E + E id  id id id id id + (id * id) (id + id) * id Arithmetic Expressions -- A Better Way The Language of Simple Arithmetic Expressions G = (V, (, R, E), where V = {+, *, (, ), id, T, F, E}, ( = {+, *, (, ), id}, R = { E ( E + T E( T T ( T * F T ( F F ( (E) F ( id } Examples: id + id * id id * id * id BNF Backus-Naur Form (BNF) is used to define the syntax of programming languages using context-free grammars. Main idea: give descriptive names to nonterminals and put them in angle brackets. Example: arithmetic expressions: (expression( ( (expression( + (term( (expression( ( (term( (term( ( (term( * (factor( (term( ( (factor( (factor( ( ((expression() (factor( ( (id( The Language of Boolean Logic G = (V, (, R, E), where V = {(, (, (,( , (, ), id, E, E1, E2, E3, E4 }, ( = {(, (, (, (, (, ), id}, R = { E ( E ( E1 E ( E1 E1 ( E1 ( E2 E1 (E2 E2 ( E2 ( E3 E2 ( E3 E3 ( ( E4 E3 ( E4 E4 ((E) E4 ( id } Boolean Logic isn't Regular Suppose it were regular. Then there is an N as specified in the pumping theorem. Let w be a string of length 2N + 1 + 2|id| of the form: w = ( ( ( ( ( ( id ) ) ) ) ) ) ( id N x y y = (k for some k > 0 because |xy| ( N. Then the string that is identical to w except that it has k additional ('s at the beginning would also be in the language. But it can't be because the parentheses would be mismatched. So the language is not regular. All Regular Languages Are Context Free (1) Every regular language can be described by a regular grammar. We know this because we can derive a regular grammar from any FSM (as well as vice versa). Regular grammars are special cases of context-free grammars.  a, b  S T  a, b (2) The context-free languages are precisely the languages accepted by NDPDAs. But every FSM is a PDA that doesn't bother with the stack. So every regular language can be accepted by a NDPDA and is thus context-free. (3) Context-free languages are closed under union, concatenation, and Kleene *, and ( and each single character in ( are clearly context free. Lecture Notes 12 Context-Free Grammars  PAGE 5 ?@{|~GNOP%&@S[\`aefm{  )*=>Rd     ( ) ? @ i źjUmHnHu6 je j j j5mHnHu56j56UmHnHuj5UmHnHu5I&>?A{ OQ>$a$$a$<>?@STl} 0`0@ ^@ )=Rcd    - D M N W n $a$i j   < > d { : ; B C D E H I W X ^ _ d e | } = >  5H*H* jejUmHnHu j5 jY  < b c d { | ! 6 7 8 @ F M O S ]^$a$S T \ b i j k 8 9 H I $a$^]  $ % b )c +E` ^` ! & F$a$ ^`    $ Q R YZ\]%&')+56<=Q`ijw$% jH* jc jb ja j 5H*\ j5\5\ j jS5 j jehN4BOblwxyU=>?efgz{$a$%=>?@CD]^fgpqy}UY>emnopuv  &067EF\]qrKe/4PT jH*5jUmHnHu j jS jY$%&'01?Uk KL$a$LMde/56PUVijk$a$*+JKSTYZefkluv   !"#$%'(,/NVWCJ0 j j j jS5\ )@RWaiq~$a$` ^`pq,/0Nf ! ^``$a$Wlmoprstu     )*4P12OP0X6;^c !Ƚ0JmHnHu0J j0JU jejUmHnHu jH*>*5 j jS j j j jJ$234PQ,TU/0XY56^s ^``$a$<0/ =!"`#`$%5 0/ =!"`#`$% P00C 0/ =!"`#`$% P0     1 0/ =!"`#`$%0(5 0/ =!"`#`$% P0 0/ =!"`#`$%? 0/ =!"`#`$% P0    0/ =!"`#$%5 0/ =!"`#$% P0 0/ =!"`#$%5 0/ =!"`#$% P0 0/ =!"`#$%5 0/ =!"`#$% P0 0/ =!"`#$% i0@0 Normal_HmH sH tH J@J Heading 1 $<5CJKHOJQJkH<A@< Default Paragraph Font,@, Header  !, @, Footer  !&)@& Page Number@dd8jg&1KL!LXLLLM(MiMMMMN:NqN#zzzzzz@mdd8NUj g&(1K}1%'&>?A{ OQ>?@STl} )=Rcd-DMNWn<bcd{| !678@FMOST\bijk89HI $ % b ) c + E     4 B O b l w x y U =>?efgz{$%&'01?Uk KLMde/56PUVijk )@RWaiq~pq,/0Nf$234PQ,TU/0XY56^s<000000000000000000000000000000000000 0 0 0 0000@0@0@00000000000000000000000000000000000@000000000000000000000000000000@0@0@0@000000000000000000000000000000000000000000000_________________________________________________________________________________bi  %W"%> S L !#$SZ\b!8RS@"RR~"(  P2  3 1?"bB @ c $1?"bB @ c $1?"&P2  3 1?"GP2  3 1?"bB  c $1?"bB  c $1?"%P2   3 1?"HP2   3 1?"bB  @ c $1?"bB  @ c $1?"$P2   3 1?"MbB  c $1?"bB  c $1?"#bB  c $1?"EbB  c $1?"bB  c $1?"bB  c $1?""bB  c $1?"LbB  c $1?"bB @ c $1?"bB @ c $1?"*bB  c $1?"FbB  c $1?"bB  c $1?"bB  c $1?")bB  c $1?"KbB  c $1?"bB @ c $1?"bB @ c $1?".   # B NC NE4F1? 9l&l&66ns>J@6F6Gl&Hl&dJLNL@ 3"JbB !@ c $1?"bB " c $1?"bB # c $1?"-bB $ c $1?"DbB % c $1?"bB & c $1?"bB ' c $1?",bB ( c $1?"IbB )@ c $1?" bB * c $1?"1 + # B NC NE(F1? N3M UL J&!G3eEd@5d@O2DMDMDM@ 3"PbB , c $1?" bB -@ c $1?"bB . c $1?"ObB /@ c $1?" bB 0 c $1?"bB 1 c $1?"NbB 2 c $1?" bB 3 c $1?"bB 4@ c $1?"bB 5@ c $1?"!bB 6 c $1?" bB 7 c $1?"bB 8 c $1?"bB 9 c $1?" bB : c $1?"bB ;@ c $1?"bB <@ c $1?"(bB = c $1?"'bB >@ c $1?"+bB ? c $1?"0bB @ c $1?"/bB A@ c $1?"7bB B@ c $1?"6bB C c $1?"5bB D c $1?"4bB E c $1?"3bB F c $1?"2bB G c $1?"?bB H c $1?">bB I c $1?"CbB J c $1?"BbB K c $1?"AbB L c $1?"@bB M c $1?"=bB N c $1?":bB O c $1?"<bB P c $1?"9bB Q c $1?";bB R c $1?"8B S  ??{|}O  )=<=y z { | U V W X /0123PQRS6789:^_`abpt;MtGtt%4 t!  +t% & t<t P)qt,m9Ot)9t2It/,4t69v%t4Ct8t:t tzt]%t"9t wDt=%t >CtCt&DtSt7t3(@t0t- @t;t90t5J !t!tt !tF1t)Ot="t< 1tT1t61t>:@t'D"t#tr"t@ *!t?H^t*AtF $tE-M tD  tC-tBtAWtRztPkltNNtQj tO[ \ tMM tH$$tG-tLtKJ<KtJ:-;tIt$c gt>+t/:t? & t t(6 v t + htX>t /wt y3p*t1Yt.h:t+J: tXZ]_bdYZ]^`a13<?JLY[fh{~?G ( * h j h j r u Y\adlp  #COKM<!" h j EIw|<::::::::::::::Alan Kaylor Cline,C:\EAR\CSWORK\LIN340\ContextFreeHandout1.docAlan Kaylor Cline4D:\EAR\CSwork\AutomataTheory\ContextFreeHandout1.docAlan Kaylor Cline4D:\EAR\CSwork\AutomataTheory\ContextFreeHandout1.docAlan Kaylor Cline4D:\EAR\CSwork\AutomataTheory\ContextFreeHandout1.docElaine Alice Rich+D:\ear\CSwork\CS341\ContextFreeHandout1.doc Donald BakerMF:\UT\CS341\Packet\CS341-Spring2002\1-LectureNotes\12-ContextFreeHandout1.doc Donald BakeriC:\WINDOWS\Profiles\dbaker\Application Data\Microsoft\Word\AutoRecovery save of 12-ContextFreeHandout.asd Donald BakeriC:\WINDOWS\Profiles\dbaker\Application Data\Microsoft\Word\AutoRecovery save of 12-ContextFreeHandout.asd Donald BakerCF:\UT\CS341\Packet\Current\1-LectureNotes\12-ContextFreeHandout.doc Don BakerCF:\UT\CS341\Packet\Current\1-LectureNotes\12-ContextFreeHandout.docbc)@PLiGu @x P^`POJQJo(@x@@^@`.@x0^`0..@x``^``...@ x^` ....@ x^` .....@ x^` ......@ x`^``.......@ x00^0`........*::^:`o(() hh^h`OJQJo(LiGubc)@h h^h`OJQJo(;@HP8000Ne01:HP LaserJet 5Si/5Si MX PSHP LaserJet 5Si/5Si MX PSHP8000W odXLetterPRIV''''0 HP8000W odXLetterPRIV''''0 P@UnknownGz Times New Roman5Symbol3& z Arial"qh"f(j&h&' .!>02Q!Grammars, Languages, and MachinesUnknown Don BakerOh+'0 (4 P \ h t"Grammars, Languages, and MachinesosramUnknownnknnkn Normal.dota Don Bakera39 Microsoft Word 9.0,@A@G@;<@`~՜.+,0 px   a|. 2 "Grammars, Languages, and Machines Title  !"#$%&')*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXY[\]^_`acdefghilRoot Entry F ~n1Table(cWordDocumentNSummaryInformation(ZDocumentSummaryInformation8bCompObjjObjectPool ~ ~  FMicrosoft Word Document MSWordDocWord.Document.89q