Problem Solving in Automata, Languages, and Complexity

146 CONTEXT-FREE LANGUAGES Recall that for any language L, MAX(L) is the set of strings 2 E L such that g is not a proper prefix ...

3.6 Pumping Lemmas for Context-Free Languages 147 /1*\ i “A’\ a* S C s a* a* (4 w Figure 3.20: (a) A marked parse tree. (b) A le ...

148 CONTEXT-FREE LANGUAGES We can prove by induction that if every path of a parse tree T contains at most i marked internal nod ...

3.6 Pumping Lemmas for Context-Free Languages 149 Example 3.53 Show that L = {bi,#bi,# l. .#bik 1 k > 2, each bij is the bina ...

150 CONTEXT-FREE LANGUAGES By the same argument as above, we get ~1 = bj and yr = cj for some j, 1 < j < m.. Now, applying ...

3.6 Pumping Lemmas for Context-Free Languages 151 Figure 3.21: Decomposition of the tree T. (2) There is a string wa, in I&, ...

152 CONTEXT-FREE LANGUAGES tree T would be more than m.. Let us fix this subtree Ti, and let T’ be the tree T with subtree Ti re ...

3.6 Pumping Lemmas for Context-Free Languages 153 Example 3.56 A language L over a singleton aZphubet (0) is context-free if an ...

154 CONTEXT-FREE LANGUAGES case of v = E and y = bj with j # n - m2. Suppose that we start with a string w = umbn, with n < m ...

3.6 Pumping Lemmas for Context-Free Languages 155 Therefore, we know that (p, q + tr) E Ta C 4(L) for all t > 0. Note that r ...

156 CONTEXT-FREE LANGUAGES (3) for any n > 0, uvnxynz E L. For each of the following languages, determine whether it is cont ...

3.6 Pumping Lemmas for Context-Free Languages 157 * 6. Show that the language {uibjc”de ( [i = j, k = !] or [; = !,j = k]} is in ...

158 CONTEXT-FREE LANGUAGES (4 wR 1 x E L and xR E L} is context-free. (e) {xxR ] x E L or xR $! L} is context-free. 0 1 xxR ] x ...

4 4.1 One-Tape Turing Machines In the previous chapters, we have studied two types of computational models: finite automata and ...

160 TURING MACHINES B a b b a B B B Figure 4.1: A one-tape DTM at the initial position. (Figure 4.1). However, DTM’s can perform ...

4.1 One-Tape Turing Machines 161 S is a transition function. (Because the blank symbol B and the final state h are common to eve ...

4.3 Multi-Tape Turing Machines (5) At a configuration (h, ~g), machine halts and accepts the input. This configuration does not ...

4.1 One-Tape Turing Machines 163 B/B, -cl L h du, R b/b, R Figure 4.2: The transition diagram of the DTM Ml. state p does nothin ...

164 TURING MACHINES one-tape DTM iV’ = (Q U {s,t}, C, CU {B},& s), where s, t $ Q, and (PAR) “(” ‘) = { (h, B, L) if a # B, ...

4.1 One-Tape Turing Machines Exercises 4.1 165 Trace DTM A&r of Example 4.1 and show the computation of Ml on inputs aabba ...