Context-FreeGrammars

← Back to document page

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: 2Example:0n1nHere is a grammar:S 0S1S Sis the only variable. The terminals are two 6a: 3Using 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: 4Example ContinuedS 0S1S The string0011is in the language derivation is:S= 0S1= 00S11= 0011For compactness, we writeS 0S1| where the vertical bar 6a: 5Example: PalindromesLetPbe language of palindromes with alpha-bet{a,b}.

String w of terminals is generated by the gram-mar if, starting with the start variable, one can apply productions and end up with w. The se-quence of strings so obtained is a derivation of w. We focus on a special version of grammars called a context-free grammar (CFG). A language is

  Context, String, Context freegrammars, Freegrammars