1 Context-Free Grammars2 Designing Context-Free Grammars3 Derivations and Parse Trees4 Designing Pushdown Automata5 Context-Free Languages and PDA's6 Parsing6.1 Parsing as Search6.2 Top Down Parsing6.3 Bottom Up Parsing7 Closure Properties of Context-Free Languages8 The Context-Free Pumping LemmaContext-Free Languages and Pushdown Automata1 Context-Free GrammarsSuppose we want to generate a set of strings (a language) L over an alphabet . How shall we specify our language? Onevery useful way is to write a grammar for L. A grammar is composed of a set of rules. Each rule may make use of theelements of (which we'll call the terminal alphabet or terminal vocabulary), as well as an additional alphabet, the non-terminal alphabet or vocabulary. To distinguish between the terminal alphabet and the non-terminal alphabet, we willuse lower-case letters: a, b, c, etc. for the terminal alphabet and upper-case letters: A, B, C, S, etc. for the non-terminalalphabet. (But this is just a convention. Any character can be in either alphabet. The only requirement is that the twoalphabets be disjoint.)A grammar generates strings in a language using rules, which are instructions, or better, licenses, to replace some non-terminal symbol by some string. Typical rules look like this:S ASa, B aB, A SaSSbB. In context-free grammars, rules have a single non-terminal symbol (upper-case letter) on the left, and any string of terminaland/or non-terminal symbols on the right. So even things like A A and B are perfectly good context-free grammarrules. What's not allowed is something with more than one symbol to the left of the arrow: AB a, or a single terminalsymbol: a Ba, or no symbols at all on the left: Aab. The idea is that each rule allows the replacement of the symbolon its left by the string on its right. We call these grammars context free because every rule has just a single nonterminal onits left. We can’t add any contextual restrictions (such as aAa). So each replacement is done independently of all theothers.To generate strings we start with a designated start symbol often S (for "sentence"), and apply the rules as many times as weplease whenever any one is applicable. To get this process going, there will clearly have to be at least one rule in thegrammar with the start symbol on the left-hand side. (If there isn't, then the grammar won't generate any strings and willtherefore generate , the empty language.) Suppose, however, that the start symbol is S and the grammar contains both therules S AB and S aBaa. We may apply either one, producing AB as the "working string" in the first case and aBaa inthe second.Next we need to look for rules that allow further rewriting of our working string. In the first case (where the working stringis AB), we want rules with either A or B on the left (any non-terminal symbol of the working string may be rewritten by ruleat any time); in the latter case, we will need a rule rewriting B. If, for example, there is a rule B aBb, then our firstworking string could be rewritten as AaBb (the A stays, of course, awaiting its chance to be replaced), and the second wouldbecome aaBbaa.How long does this process continue? It will necessarily stop when the working string has no symbols that can be replaced.This would happen if either:(1) the working string consists entirely of terminal symbols (including, as a special case, when the working string is , theempty string), or(2) there are non-terminal symbols in the working string but none appears on the left-hand side of any rule in the grammar(e.g., if the working string were AaBb, but no rule had A or B on the left).In the first case, but not the second, we say that the working string is generated by the grammar. Thus, a grammargenerates, in the technical sense, only strings over the terminal alphabet, i.e., strings in *. In the second case, we have ablocked or non-terminated derivation but no generated string.It is also possible that in a particular case neither (1) nor (2) is achieved. Suppose, for example, the grammar containedonly the rules S Ba and B bB, with S the start symbol. Then using the symbol to connect the steps in the rewritingprocess, all derivations proceed in the following way:S Ba bBa bbBa bbbBa bbbbBa ...The working string is always rewriteable (in only one way, as it happens), and so this grammar would not produce anyterminated derivations, let alone any terminated derivations consisting entirely of terminal symbols (i.e., generated strings).Thus this grammar generates the language .Supplementary Materials Context-Free Languages and Pushdown Automata 1Now let us look at our definition of a context-free grammar in a somewhat more formal way. A context-free grammar(CFG) G consists of four things:(1) V, a finite set (the total alphabet or vocabulary), which contains two subsets, (the terminal symbols, i.e., the ones thatwill occur in strings of the language) and V - (the nonterminal symbols, which are just working symbols within thegrammar).(2) , a finite set (the terminal alphabet or terminal vocabulary).(3) R, a finite subset of (V - ) x V*, the set of rules. Although each rule is an ordered pair (nonterminal, string), we’llgenerally use the notion nonterminal string to describe our rules.(4) S, the start symbol or initial symbol, which can be any member of V - .For example, suppose G = (V, , R, S), whereV = {S, A, B, a, b}, = {a, b}, and R = {S AB, A aAa, A a, B Bb, B b}Then G generates the string aaabb by the following derivation:(1) S AB aAaB aAaBb aaaBb aaabbFormally, given a grammar G, the two-place relation on strings called "derives in one step" and denoted by (or by G if wewant to remind ourselves that the relation is relative to G) is defined as follows:(u, v) iff strings w, x, y V* and symbol A (V - ) such that u = xAy, v = xwy, and (A w) R.In words, two strings stand in the "derives in one step" relation for a given grammar just in case the second can be producedfrom the first by rewriting a single non-terminal symbol in a way allowed by the rules of the grammar.(u, v) is commonly written in infix notation, thus: u v. This bears an obvious relation to the "yields in one step" relation defined
View Full Document
Unlocking...