Context-FreeGrammars

1 context -Free GrammarsA grammar is a set of rules for putting stringstogether and so corresponds to a of: a set ofvariables(also called nonterminals),one of which is designated the start variable;It is customary to use upper-case letters forvariables; a set ofterminals(from the alphabet); and a list ofproductions(also called rules).Goddard 6a: 2 Example:0n1nHere is a grammar:S 0S1S Sis the only variable. The terminals are two 6a: 3 Using a GrammarA production allows one to take a string con-taining a variable and replace the variable bythe RHS of the terminals isgeneratedby the gram-mar if, starting with the start variable, one canapply productions and end up withw. The se-quence of strings so obtained is focus on a special version of grammars calledacontext-free grammar(CFG). A language iscontext-freeif it is generated by a 6a: 4 Example ContinuedS 0S1S The string0011is in the language derivation is:S= 0S1= 00S11= 0011 For compactness, we writeS 0S1| where the vertical bar 6a: 5 Example: PalindromesLetPbe language of palindromes with alpha-bet{a,b}.

2 One can determine a CFG forPbyfinding a recursive we peel first and last symbols from a palin-drome, what remains is a palindrome; and if wewrap a palindrome with the same symbol frontand back, then it is still a isP aPa|bPb| Actually, this generates only those of even length..Goddard 6a: 6 Formal DefinitionOne can provide aformal definitionof a context -free grammar. It is a 4-tuple(V, , S, P)where: Vis a finite set of variables; is a finite alphabet of terminals; Sis the start variable; and Pis the finite set of productions. Eachproduction has the formV (V ) .Goddard 6a: 7 Further Examples: Even0 sA CFG for all binary strings with an even num-ber of0 the decomposition. If first symbol is1,then even number of0 s remain. If first sym-bol is0, then go to next0; after that again aneven number of0 s remain. This yields:S 1S|0A0S| A 1A| Goddard 6a: 8 Alternate CFG for Even0 sHere is another CFG for the same that when first symbol is0, what remainshas odd number of0 6a: 9 Alternate CFG for Even0 sHere is another CFG for the same that when first symbol is0, what remainshas odd number of0 1S|0T| T 1T|0 SGoddard 6a: 10 ExampleA CFG for the regular language correspondingto the RE00 11.

3 Goddard 6a: 11 ExampleA CFG for the regular language correspondingto the RE00 11 .The language is the concatenation of two lan-guages: all strings of zeroes with all strings CDC 0C|0D 1D|1 Goddard 6a: 12 Example ComplementA CFG for the complement of RE00 11 .CFGs don t do and s, but they do do or s . Astringnotof the form0i1jwherei, j >0is oneof the following: contains10; is only zeroes; oris only ones. This yields CFG:S A|B|CA D10DD 0D|1D| B 0B|0C 1C|1 Goddard 6a: 13 Consistency and CompletenessNote that to check a grammar and descriptionmatch, one must check two things: that every-thing the grammar generates fits the description(consistency), and everything in the descriptionis generated by the grammar (completeness).Goddard 6a: 14 ExampleConsider the CFGS 0S1S|1S0S| The string011100is generated:S= 0S1S= 01S= 011S0S= 0111S0S0S= 01110S0S= 011100S= 011100 What does this language contain?

4 Certainly ev-ery string generated has equal0 s and1 s..But can any string with equal0 s and1 s begenerated?Goddard 6a: 15 Example Argument for CompletenessYes. All strings with equal0 s &1 s are gener-ated:Well, at some point, equality between0 s and1 sis reached. The key is that if string starts with0,then equality is first reached at a1. So the por-tion between first0and this1is itself an ex-ample of equality, as is the portion after is, one can break up string as0w1xwithbothwandxin the break-up of00101101:0 0 1 0 1 1 0 1wxGoddard 6a: 16A Silly Language CFGThis CFG generates sentences as composed ofnoun- and verb-phrases:S NPVPNP theNVP VNPV sings|eatsN cat|song|canaryThis generates the canary sings the song , butalso the song eats the cat .This CFG generates all legal sentences, notjust meaningful 6a: 17 PracticeGive grammars for the following two languages:1.

5 All binary strings with both an even numberof zeroes and an even number of All strings of the form0a1b0cwherea+c=b.(Hint: it s the concatenation of two simplerlanguages.)Goddard 6a: 18 Practice Solutions1)S 0X|1Y| X 0S|1Z(odd zeroes, even ones)Y 1S|0Z(odd ones, even zeroes)Z 0Y|1X(odd ones, odd zeroes)2)S TUT 0T1| U 1U0| Goddard 6a: 19 SummaryA context -free grammar (CFG) consists of a setof productions that you use to replace a vari-able by a string of variables and terminals. Thelanguage of a grammar is the set of strings itgenerates. A language is context -free if there isa CFG for 6a: 20