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)