Problem Solving in Automata, Languages, and Complexity

(^126) CONTEXT-FREE LANGUAGES b,E /b b,a IE c, b/e Figure 3.13: Solution to Example 3.30. 0 a a, E/a Figure 3.14: Solution to Ex ...

3.4 Pushdown Automata 127 input tape and accept the input. There is a subtle problem with the second case. That is, it is possib ...

128 CONTEXT-FREE LANGUAGES Figure 3.15: Solution of Example 3.32. To see that this PDA M correctly accepts the language L, we no ...

3.4 Pushdown Automata 129 b,a /E a,b /E b,c Lb a, E/a Figure 3.16: Solution of Example 3.33. (s, ababaab, E) I- (~1, babaab, a) ...

130 CONTEXT-FREE LANGUAGES Figure 3.17: Solution of Example 3.34. Example 3.34 Construct a PDA M that accepts the language L = - ...

3.4 Pushdown Automata 131 path of your PDA on X. (a) {unbm 1 m,n > 0,m # 3n); x = a2b4. (b) {unbm IO < 2; < m < 3n); ...

132 (4 CONTEXT-FREE LANGUAGES (We assume that the PDA starts with a special symbol $ in the stack, i.e., the initial configurati ...

3.5 Pushdown Automata and Context-Free Grammars 133 by the technique of Example 3.31, using extra temporary states to push extra ...

134 CONTEXT-FREELANGUAGES Figure 3.18: PDA for Example 3.36 the accepting computation path of PDA M is (5 aab, E) I- (CL aab, S) ...

(2) For each instruction (p, BA ) E d’(q, a, A), where IBI = 1 and a E ~U{E}, we define the rules , T’) (T’, A, r), for all r, r ...

136 CONTEXT-FREE LANGUAGES Then, we must have 1 < IyI < 2 (the PDA M’ must read a symbol from the stack to-operate, and SO ...

3.5 Pushdown Automata and Context-Free Grammars 137 (1) We observe that the PDA M cannot move from p to q, nor from f to p OF q. ...

138 CONTEXT-FREE LANGUAGES We observe that the construction in the proof of Theorem 3.37 is very tedious and the resulting conte ...

3.5 Pushdown Automata and Context-Free Grammars 139 A = (O”‘l”‘O”21”” l **0”k17nk 1 m1,nz2,.. .,mk > 1,k > - 1), ~~{O~~~~~ ...

140 CONTEXT-FREE LANGUAGES It is clear that the above PDA M accepts z$ if and only if there ex- ists a computation path of Ml th ...

3.5 Pushdown Automata and Context-Free Grammars 141 S(q1, Xyz) = S(qj, yZ) = s(4kT z) = !It E Fe Correspondingly, the PDA @ acce ...

142 CONTEXT-FREE LANGUAGES * (d) (0, q* - {h#b+1 I bi is the binary representation of i, i > - 1). Show that if L is a regul ...

3.6 Pumping Lemmas for Context-Free Languages 143 means that, in any parse tree under grammar G, every vertex has at most d chil ...

144 CONTEXT-FREE LANGUAGES T2 $2 V Y T3 X Figure 3.19: Proof of the pumping lemma. this longest path plus the ancestors of qi wo ...

3.6 Pumping Lemmas for Context-Free Languages 145 Solution. Suppose, to the contrary, that L is a context-free language and G is ...