Transcription of Context-FreeGrammars
{{id}} {{{paragraph}}}
Example: marketing
Context-FreeGrammars
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}.
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
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: