Problem Solving in Automata, Languages, and Complexity

106 CONTEXT-FREE LANGUAGES and Gy = (0, {O,l}Ry,A), with Then, X = L(Gx) and Y = L(Gy). C om b ining them together, we get the g ...

3.2 Examples of Context-Free Grammars 107 (a) If bi = 1” for some k > 0 then bi+l = 10’“. (b) If bi = ~01’” for some u E l(0 ...

108 CONTEXT-FREELANGUAGES T + 1TO 1 lE#l 1 l#lOOD, W + lW0 1 lE#Al 1 #AlOD, S6 + UlD I VlD I AlPlD I AOQlD, U + OUO 1 OUl 1 lU0 ...

3.3 Parsing and Ambiguity 109 4. (b) {aibjc”de 1 i + k 5 j + e+ 3). * (c) {dbjc”d~ 1 i + 2k = j + 3&}. * (d) {aitickde 1 i + ...

110 CONTEXT-FREE LANGUAGES S S /I\ S b S /\\ /I\ A\ c i S b S a! (^60) (b) Figure 3.4: The sentence abaca has two parse trees. c ...

3.3 Parsing and Ambiguity 111 Thus, a parse tree of a string IX: demontrates the structure of the generation of x from the gramm ...

112 CONTEXT-FREE LANGUAGES scs (a) If 5 a vertex then we ScSbS abad, abSbScS abScScS / I I \ \ I \ \ 1 . abacSbS abacScS Figure ...

3.3 Parsing and Ambiguity I I Figure 3.6: A parse tree for X. Example 3.23 Consider the following grammar G, in which a word of ...

114 CONTEXT-FREE LANGUAGES if Figure 3.7: Another parse tree for (xf. (a) (b) Figure 3.8: Two parse trees for a + a * a. Example ...

3.3 Parsing and Ambiguity 115 represent operands of operations + and -, and use symbol F (standing for factor) to represent oper ...

116 CONTEXT-FREE LANGUAGES E /I\ E -I- T /I\ I E I T I I I F F a I I a b E - T /I\ * F /I‘\ F F c E > I I b /I\ a Et-T I I T ...

3.3 Parsing and Ambiguity 117 nn abaabb 1 J is incorrect, since we should match the first two symbols a and t, as soon as they a ...

118 CONTEXT-FREE LANGUAGES Finally, we observe that if z is generated by X from the derivation (3.1), then au must be the longes ...

3.3 Parsing and Ambiguity 119 analysis of context-free grammars. We delay it until Secion 3.5 (see Example 3.54). Lookahead Sets ...

120 CONTEXT-FREE LANGUAGES and where (A + X) and (A --+ y) are two distinct A-rules. This implies that w’ belongs to both LA(A - ...

3.3 nursing and Ambiguity 121 (b) Show that this grammar is unambiguous. Let G be the context-free grammar with rules S ---+ A ...

122 CONTEXT-FREE LANGUAGES 3.4 Pushdown Automata Context-free grammars are generators for context-free languages, from which we ...

3.4 Pushdown Automata 123 the operation as in the case of (p, V) E s(4, a, u), except that it does not read a tape symbol (and s ...

124 CONTEXT-FREE LANGUAGES b,c a, E/a /b Figure 3.11: Transition diagram of PDA M of Example 3.28. c = (p, y, y) and Ci t- Ci+l ...

3.4 Pushdown Automata 125 b,E a, E/a Lb Figure 3.12: Solution to Example 3.29. Example 3.29 Construct a PDA accepting the langua ...