ࡱ> dfck bjbj G}}lvvvvvvv<dZ` ` ` ` ` ]L]L]L&W(W(W(WAiWPXP Z$>[ ^]t-Zv]LCF ]L]L]L-Z Qvv` ` "BZ Q Q Q]Lv` v` &W Q]L&W Qd QqVV[vvW` T ~O WW XZ0ZW]Pp]W Q&vvvvContext-Free Grammars, Languages, and Pushdown Automata   L Context-Free Language   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 wis 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}, R = 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 /* at least one extra a generated A ( aA A ( aAb B ( b /* at least one extra b generated 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, 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. ;=Mehj{|+245 "#*8=>?@DELMTU[\cdlm Ioƹ jCJ0jCJ0UmHnHu6CJ0 jeCJ0 jCJ0 jCJ05CJ0 jCJ0 56CJ8j5CJ8UmHnHu5CJ8F89:;h346?Ix @ ^@  y &#$/$a$  ):AIQX_hqrs~0`0@ ^@  %Iop(@ARSZbjr$a$#$:;BRVW]^efmnuv|} 7        ! 8 9 < = A B G H O P Q R U V F G W X e f s t 5CJ0H*CJ0H* jeCJ05CJ8jCJ0UmHnHu jCJ05CJ0 jCJ0CJ0Pry    7 8    ]^$a$   % & ' > ? E M S Z [   A B H I Y g u v $a$^]v ! ! N O Fey` ^` & F$a$ ^`       K L O Q R S V v w jCJ0CJ0H* jcCJ0 jbCJ0 jaCJ0 jCJ0 5CJ0H*\ j5CJ0\ 5CJ0\ jCJ0 jSCJ05CJ8 jeCJ0h jCJ0CJ0 je j? '(7DJahijkqrs{ !-.6;IO+-=>Ou|}~ jCJ0CJ0H*jCJ0UmHnHu jCJ0 jCJ05CJ8 jSCJ0 jCJ0 5CJ0\ jCJ0CJ0H*CJ0I &456I+o<INuv$a$07?ipy*@A^j$a$ 239:ABklstz,-67CDSVdgil BCste jCJ0 jCJ0 B*phjCJ0UmHnHu jSCJ05CJ8 jCJ0CJ0Rjk"1>MRSdhi  $a$ 9:Rrde$a$ ^`` ^`/C]r &0@KXcn{$a$` ^`     "#&'-.126789:;ABCDJKLMOPZ[_`fghijkmns jCJ0 jCJ0 jCJ0 jCJ0 jSCJ05CJ8 jCJ0 jCJ0 jCJ0CJ0O!",-067;<@FGQRST^_ijtu{|-8HI{|xz{JKij jSCJ0 jeCJ0jCJ0UmHnHu jCJ0CJ0H*>*CJ05CJ8 B* CJ0ph3 j j jCJ0 jCJ0 jCJ0 jCJ0CJ0B$%M`uvxyz$a$/ =!"`#`$%5 0/ =!"`#`$% P00C 0/ =!"`#`$% P0     1 0/ =!"`#`$%0(5 0/ =!"`#`$% P0 0/ =!"`#`$%? 0/ =!"`#`$% P0    0/ =!"`#`$% i0@0 Normal_HmH sH tH @@@ Heading 1$@&^`CJ00@0 Heading 2$@&CJ0<A@< Default Paragraph Font4B@4 Body Text B* CJ0ph3.P@. Body Text 2CJ0s&FFUFFFG%GfG!z#zzzzzzz z z z z zzzzy*sJB  & O zs|{%&&  &   '89:;h346?Ix  ):AIQX_hqrs~ %Iop(@ARSZbjry78  %&'>?EMSZ[ABHIYguv !! N O  F e y  & 4 5 6 I + o  < I N u v 07?ipy*@A^jk"1>MRSdhi  9:Rrde/C]r &0@KXcn{$%M`uvxyz000000000000000000000000`00000000000000`000000000000000000`0000000`00000000000000000000000000000`0000000000`0000000000`0000000000000000000000000000000000 0 0 0 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000  ! r v j "8PQ@n"PP!(   B2 .@ 3 1? P2  3 1?"bB @ c $1?" bB @ c $1?"bB @ c $1?"P2  3 1?"KP2  3 1?"bB  c $1?" bB   c $1?"bB   c $1?"P2   3 1?"JP2   3 1?"bB  @ c $1?" bB @ c $1?"bB @ c $1?"$P2  3 1?"IbB  c $1?" bB  c $1?"bB  c $1?"#0  # B NC NEdF1?7n2--B)+ q + + F/2+ 8V<&==4? ^E-I7J;J.@K.@ LD LMNM@3"HbB  c $1?"bB @ c $1?"bB  c $1?"bB  c $1?""L  # B NC NEF1? MnMba# 1 1 818??bFFM6M38F&9?:?;8d>8>1K@1?At*Bt*Da#|Fa#pGMH:I'K'K'MMN@3"NbB  c $1?"bB  c $1?" bB @ c $1?"bB @ c $1?"(bB  c $1?"MbB  c $1?"bB   c $1?"bB ! c $1?"'bB " c $1?"LTB #@ c $1?bB $@ c $1?"bB %@ c $1?"-bB & c $1?"GTB '@ c $1?bB ( c $1?"bB ) c $1?",bB *@ c $1?"FP2 +@ 3 1?"bB , c $1?"bB - c $1?"+bB / c $1?"/bB 0 c $1?"EbB 1@ c $1?"bB 2 c $1?"BbB 3 c $1?"bB 4 c $1?"DbB 5 c $1?"bB 6 c $1?"CbB 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?"5bB @ c $1?"4bB A c $1?"3bB B@ c $1?"2bB C c $1?"1bB D c $1?"0bB E c $1?"8bB F@ c $1?"=bB G c $1?"<bB H c $1?";bB I@ c $1?":bB J c $1?"7bB K c $1?"9bB L c $1?"6bB M c $1?"AbB N c $1?"@bB O c $1?">bB P c $1?"?B S  ?/ +.;<hi46 7 8 9 : I J K L M N + , STUdefijk`@ at`a$ t "t+  t#)dVt'1t.t01 t $ th}I&t(I&t-t -YttQtvt  t0  t  t1t(xQt$XttAt,tt5$t3| }t1 }t 8 }t2]#t9T!t8hist7}t t0 1 _t t;h t:Ut!0 ] t t=t<Dqt-L  {t)  {t%  t>< = t/L .M tD`/%|tC`/atB$/MtA xt@xt?tL(%)%tJ'}tE'tKtItHt KtGt 7u ptFD 7u tOtPtNttM/`t2t6(tt4x{yt03Dt*PYt&Yt 3YtH ,t #Q t#It"kI ,t! <tpt!FHNPegnp_agioq"$7:ILWYadprHT & * " $ / 2 i l q t {  46;>uxag<BNPnp_aO P   & ( f g @ D 0178 26DJ`fvz%&opvw::::::::::::::::::::::::::::::::    ^^Alan Kaylor Cline+C:\EAR\CSWORK\LIN340\ContextFreeSlides1.docAlan Kaylor Cline+C:\EAR\CSWORK\LIN340\ContextFreeSlides1.docAlan Kaylor Cline+C:\EAR\CSWORK\LIN340\ContextFreeSlides1.docAlan Kaylor Cline+C:\EAR\CSWORK\LIN340\ContextFreeSlides1.docAlan Kaylor Cline3D:\EAR\CSwork\AutomataTheory\ContextFreeSlides1.docElaine Alice Rich*D:\ear\CSwork\CS341\ContextFreeSlides1.docdbaker5F:\UT\CS341\Slides\ContextFree\ContextFreeSlides1.doc Donald BakerfC:\WINDOWS\Profiles\dbaker\Application Data\Microsoft\Word\AutoRecovery save of ContextFreeSlides1.asd Donald Baker5F:\UT\CS341\Slides\ContextFree\ContextFreeSlides1.doc Don Baker5F:\UT\CS341\Slides\ContextFree\ContextFreeSlides1.doc*DP @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"qh9|!'j&"j&-m +Q>0d-2QContext-Free GrammarsUnknown Don BakerOh+'0 ( D P \ ht|Context-Free Grammars9ontUnknownnknnkn Normal.dote Don Bakere45 Microsoft Word 9.0r@^v$@!~@"@~m՜.+,0  px  xv+ 2 Context-Free Grammars Title  !"#%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRTUVWXYZ\]^_`abeRoot Entry Fx9~g1Table$]WordDocumentGSummaryInformation(SDocumentSummaryInformation8[CompObjjObjectPoolx9~x9~  FMicrosoft Word Document MSWordDocWord.Document.89q