CS 21 Decidability and Tractability Winter 2024
Out: February 7
Midterm Solutions
If you have not yet turned in the Midterm you should not consult these solutions.
Copyright By PowCoder代写 加微信 powcoder
The language L1 is not context-free.
To see it is not context-free, we use the CFL pumping lemma: let w = apbpcpdp, and consider the ways w can be written as w = uvxyz. If u or v straddles the boundary between characters, then pumping results in an out-of-order string (not in the language). Otherwise, we use the fact that |vxy| ≤ p to argue that v and y can only be within a single block or two adjacent blocks of characters. In all such cases, pumping on v and y results in a string not in the language. We conclude that L1 is not context free.
Decidable. We will reduce this problem to ECFG (emptiness of context-free-grammars), which we saw in lecture was decidable. Given E we first build the DFA that recognizes language A, the complement of L(E). This is possible because regular languages are closed under complement. We also know how to construct a NPDA that recognizes the language B = L(G) ∩ A (from the hint: Sipser problem 2.18). We now check if B is empty. From lecture we know that emptiness of CFGs is decidable. Moreover the com- plementation step and the intersection step are all computable transformations. Finally, note that B is empty iff L(G) ⊆ L(E), so the language CFG-IN-REG is decidable.
(b) Undecidable. We reduce ALLCFG to REG-IN-CFG. Set E = Σ∗. Given an instance G of ALLCFG, we produce the pair (E,G). If G = Σ∗ then clearly L(E) ⊆ L(G); if G ̸= Σ∗ then L(E) ̸⊆ L(G). Therefore we have reduced ALLCFG to REG-IN-CFG, and we know from lecture that ALLCFG is undecidable.
Suppose there exists a decidable language D such that L1 ∩ D = ∅ and L2 ⊆ D, with a corresponding TM MD. Then considering MD(⟨MD⟩) we come to a contradiction as follows.
Suppose MD(⟨MD⟩) accepts; i.e. ⟨MD⟩ is in the language D. Then by the definition of L1, ⟨MD⟩ is in the language L1, which contradicts the fact that L1 ∩ D = ∅.
Suppose MD(⟨MD⟩) rejects; i.e. ⟨MD⟩ is not in the language D. Then by the definition of L2, ⟨MD⟩ is in the language L2, which contradicts the fact that L2 ⊆ D.
(a) Let G be a right-linear CFG. We will construct a NFA M recognizing L(G). Our machine M will have a single state for each non-terminal in the grammar, a distinguished “accept” state, and other states. The start state of M is the state corresponding to the start symbol in the grammar. For each transition of the form:
A → x1x2 …xnB
(b) The language L2 is context-free but not regular. To see it is context free, consider the NPDA that first pushes a’s onto the stack until it sees the first b, then pushes b’s onto the stack until it sees the first c, then pops b’s from the stack as it reads c’s, and finally pops a’s from the stack as it reads d’s. To see that it is not regular, we use the pumping lemma. Let w = apbpcpdp and consider the ways w can be written as xyz. If string y straddles the boundary between characters, then pumping on y results in an out-of-order string (not in the language). Otherwise pumping on y increases the number of only a single character type, again resulting in a string not in the language. We conclude that L2 is not regular.
(c) The language L3 is regular: it is the union of the regular languages a1000a∗b∗c∗ and the finite (and hence regular) language {anbncn : n < 1000}.
we add n − 1 states s1,s2,...,sn−1 “linking” A to B, with a transition from A to s1 labelled x1, a transition from s1 to s2 labelled x2, etc..., and a transition from sn−1 to B labelled xn.
For each transition of the form:
A → x1x2 ...xn
we add n − 1 states s1, s2, . . . , sn−1 “linking” A to the accept state, with a transition from A to s1 labelled x1, a transition from s1 to s2 labelled x2, etc..., and a transition from sn−1 to the accept state labelled xn.
Now, if M accepts a string w, then the sequence of “non-terminal” states it traverses to reach the accept state dictates a derivation of w in the grammar. In the other direction, if w has a derivation in the grammar, then it must arise from applying a sequence of rules of the first type, followed by a single application of a rule of the second type. This derivation dictates a path from the start state of M to the accept state, and thus M accepts w.
(b) Given a FA M, we construct a right-linear CFG G as follows. The non-terminals of G are exactly the states of M. The start symbol of G is the start state of M. For each transition in M from state A to state B, labelled with the symbol x, we add the following rule: A → xB. For each transition from state A to an accept state B, labelled with the symbol x, add the following rule: A → x.
If M accepts a string w, then the sequence of states traversed from the start state to an accept state dictates a derivation of w in the grammar. In the other direction, if w has a derivation in the grammar, then this derivation dictates a path from the start state of M to an accept state (since it must end with a rule of the second type).
(c) Consider the following linear CFG G:
S → 0A|1B|0|1|ε A → S0
We prove two claims to establish that this indeed generates exactly the palindrome language L. First, we claim that L ⊆ L(G). Let w be a palindrome. Since w is a palindrome, it has the form w = xxR or w = x0xR or w = x1xR, where xR denotes the reverse of string x (the latter two cases are when w is of odd length). We prove that each of these three types of strings are in L(G), by induction on |x|. If |x| = 0 then x = ε and w is either ε, 0, or 1, and indeed S derives w. Now assume by induction that for all x′ with length < n, the strings x′(x′)R, x′0(x′)R, x′1(x′)R are in L(G). Then we can derive w as follows: if the first character of x is 0, then we use one of the derivations (for the three different forms for w)
S ⇒0A⇒0S0⇒∗ 0x′(x′)R0 S ⇒ 0A ⇒ 0S0 ⇒∗ 0x′0(x′)R0 S ⇒ 0A ⇒ 0S0 ⇒∗ 0x′1(x′)R0
= xxR = x0xR = x1xR
similarly, if the first character of x is 1, then we use one of the derivations (for the three different forms for w)
S⇒1B⇒1S1⇒∗ 1x′(x′)R1 = xxR S ⇒ 1B ⇒ 1S1 ⇒∗ 1x′0(x′)R1 = x0xR S ⇒ 1B ⇒ 1S1 ⇒∗ 1x′1(x′)R1 = x1xR
In all of the above, the “⇒∗” follows by induction.
Second, we claim that L(G) ⊆ L. Consider a derivation of some string w. The proof is by induction on the length of the derivation. If the length is 1, then the only string w could be is ε, 0, or 1 and all of these strings are in L. Otherwise, assume all derivations of length < n result in strings in L and consider the first step in a length n derivation. If it is S → 0A, then the only rule that can be applied next is A → S0, so we deduce that thederivationhastheformS⇒0A⇒0S0⇒∗ 0w′0=w. NowsinceS⇒∗ w′ infewer than n steps, we know that w′ is a palindrome, and thus w = 0w′0 is as well. Otherwise, the first step in the derivation is S → 1B, then the only rule that can be applied next is B→S1,sowededucethatthederivationhastheformS⇒1B⇒1S1⇒∗ 1w′1=w. Now since S ⇒∗ w′ in fewer than n steps, we know that w′ is a palindrome, and thus w=1w′1isaswell. Weconcludethatw∈LandthenthatL(G)⊆L.
5. Let M be a recognizer for L. We are given an input #x1#x2#···#xk# for some k ≥ 0. We simulate M on each xi in parallel, and accept as soon as “three in a row” of these simulations accept. Specifically, we do the following for j = 1, 2, 3, . . .: simulate M on each xi for j steps, and if “three in a row” of the simulations halt and accept, then we halt and accept.
Now, it is clear that if for some i, all of xi, xi+1, xi+2 are in L, then for some j (corresponding to the maximum number of steps for M to accept each of xi, xi+1,xi+2) the new machine will accept. Otherwise, we will never experience accepts for “three in a row” of the xi and the machine will not accept.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com