# Context Free Grammars Definition of a grammar G

Context Free Grammars Definition of a grammar G Deriving strings and defining L(G) Context-Free Language definition 1 Context-Free Grammars Definition 2 Definition A context-free grammar G = (V, , S, P)

V: finite set of variables (nonterminals) : finite set of characters (terminals) S: start variable element of V role is similar to that of q0 for an FSA or NFA P: finite set of grammar rules or production rules Syntax of a production variable string of variables and terminals 3 English Context-Free Grammar ECFG = (V, , S, P)

V = {, , , ... } people sometimes use < > to delimit variables In this course, we generally will use capital letters to denote variables = {a, b, c, ..., z, ;, ,, ., ...} S = P = { ,

, ...} 4 {aibi | i>0} CFG ABG = (V, , S, P)

V = {S} = {a, b} S=S P = {S aSb, S ab} or S aSb | ab second format saves some space 5 Context-Free Grammars Deriving strings, defining L(G), and defining context-free languages 6

Defining , ==> notation First: notation This is used to define the productions of a grammar S aSb | ab Second: ==>G notation This is used to denote the application of a production rule from a grammar G S ==>ABG aSb ==>ABG aaSbb ==>ABG aaabbb We say that string S derives string aSb (in one step) We say that string aSb derives string aaSbb (in one step) We say that string aaSbb derives string aaabbb (in one step)

We often omit the grammar subscript when the intended grammar is unambiguous 7 Defining ==> continued Third: ==>kG notation This is used to denote k applications of production rules from a grammar G S ==>2ABG aaSbb We say that string S derives string aaSbb in two steps aSb ==>2ABG aaabbb

We say that string aSb derives string aaabbb in two steps We often omit the grammar subscript when the intended grammar is unambiguous 8 Defining ==> continued Fourth: ==>*G notation This is used to denote 0 or more applications of production rules from a grammar G S ==>*ABG S We say that string S derives string S in 0 or more steps

S ==>*ABG aaSbb We say that string S derives string aaSbb in 0 or more steps aSb ==>*ABG aaSbb We say that string aSb derives string aaSbb in 0 or more steps aSb ==>*ABG aaabbb We say that string aSb derives string aaabbb in 0 or more steps We often omit the grammar subscript when the intended grammar is unambiguous 9

Defining derivations * Derivation of a string x The complete step by step derivation of a string x from the start variable S Key fact: each step in a derivation makes only one application of a production rule from G Example: Derivation of string aaabbb using ABG S ==>ABG aSb ==>ABG aaSbb ==>ABG aaabbb Example 2: AG= (V, , S, P) where P = S SS | a Deriving string aaa S ==> SS ==> Sa ==> SSa ==> aSa ==> aaa

10 Defining L(G) * Generating strings If S ==>G* x, then grammar G generates string x Note G generates strings which contain terminals and nonterminals aSb contains nonterminals and terminals S contains only nonterminals aaabbb contains only terminals L(G)

The set of strings over generated by grammar G Note we only consider terminal strings generated by G {aibi | i > 0} = L(ABG) {ai | i > 0} = L(AG) 11 Context-Free Languages * Context-Free Languages A language L is a context-free language (CFL) iff Results so far

{ai | i > 0} is a CFL One CFG G such that L(G) = this language is AG Note this language is also regular {aibi | i > 0} is a CFL One CFG G such that L(G) = this language is ABG Note this language is NOT regular 12 Example Let BAL = the set of strings over {(,)} in which the parentheses are balanced Prove that BAL is a CFL

To prove this, you need to come up with a CFG BALG such that L(BALG) = BAL BALG = (V, , S, P) V = {S} = {(, )} S=S P=?

Give derivations of ((( ))) and ( )(( )) with your grammar 13 Implications Given that the language of balanced parentheses is a CFL, what implications does this have for compiler design? What programming language structures can be captured by CFG? 14

## Recently Viewed Presentations

• money for lunch. You stayed up all ... and humor to solve riddles. Includes: 12 Riddle Cards. Print, cut and laminate. Teacher reads card. Student who answers correctly receives the card. Student with the most cards wins! Watch out for...
• Or, once you know the time T from the tracer study, you can back-calculate to determine the baffling factor of the clearwell Baffling factor (%) = Time (min) x Flow During Tracer Study (gpm) Clearwell Volume During Tracer Study (gal)...
• Environmental Microbiology-Laboratory Manual-prepared for Environmental MicrobiologyIVBiochemical Activity of microorganism. ... Thermolabile (denaturated by heat) ... Environmental Microbiology -Laboratory Manual- prepared for Environmental Microbiology IV Biochemical Activity
• Please practice letters, sounds, and sight words, as well as, read with your student every night. is for… Snack We have an afternoon snack every day. Please make healthy choices and remember we are peanut free. is for… Teachers Students...
• "Harrison Bergeron & Examination day" Outline Using Structure to enhance storytelling While each used the same theme and structure, Vonnegut and Slesar told very different stories through "Harrison Bergeron" and "Examination Day."
• DROWNING PREVENTION Getting The Word Out Presented by Getting the Word Out Marketing 101 Effective Message Delivery Reach, Throw, Row, Don't Go Reach Reaching the right audience Not everyone's message Define the "Who" Know their demographics Use Lowest Common Denominator...
• Enzymatic Browning. Enzymatic browning occurs because of a series of reactions catalyzed by the enzyme tyrosinase. This is the same process that happens to avocado when you make guacomole. Citric acid (from limes, for example) helps to slow the process...
• Single women entered employment as teachers. Western Europe and the U.S. Closer to 20th century women began to enter the business world as secretaries and telephone operators. Women allowed to vote only after WWI (1918) ... xxx Last modified by: