For bit \(b\in\{0,1\}\) and string \(w\in\{0,1\}^*\) define \(\texttt{Count}(b,w)\) to be the number of times bit \(b\) appears in string \(w\). For example, \(\texttt{Count}(0,00101110)=4\) since there are four \(0\)’s in \(00101110\). Use the Pumping lemma for context free languages (Theorem 2.34 on page 125) to show that the following language over \(\Sigma=\{0,1,\#\}\) is not a context-free language:
\[ L = \{ x\#y \ |\ \texttt{Count}(0,x)=\texttt{Count}(0,y) \mbox{ and } \texttt{Count}(1,x)=\texttt{Count}(1,y) \}\]
Note on the language: This is saying that \(x\) and \(y\) have the same bits, but possibly in a different order — in other words, \(y\) is a permutation of \(x\).
Consider the following CFG:
\[ \begin{array}{l} S \rightarrow T\dashv \\ T \rightarrow T + \texttt{a}\ |\ \texttt{a}\\ \end{array} \]
Draw out the DFA \(DK\) that is constructed for performing the DK-test.
Use \(DK\) to parse the input \(\texttt{a}+\texttt{a}+\texttt{a}\dashv\), showing each step like we did in class.
Extra credit: Draw a DPDA from \(DK\), using the procedure sketched in the textbook’s proof for Lemma 2.58 (page 147).
Consider the following CFG:
\[ \begin{array}{l} S \rightarrow C1A\dashv \\ A \rightarrow AB\ |\ \varepsilon\\ B \rightarrow 0 | 1\\ C \rightarrow BCB | 0A\# \\ \end{array} \]
Draw out the DFA \(DK\) that is constructed for performing the DK-test. (Self-check hint: \(DK\) will have 14 states, 8 of which are accepting states.)
For each accepting case, mark whether the two DK-test conditions (on page 143, directly above Theorem 2.52) are met. If they are not met, explain why not.
Is this grammar a DCFG?
Consider Turing machine \(M_1\) from Example 3.9 (page 173). Give the sequence of configurations that \(M_1\) enters when started with each of the following input strings (note that this is similar to Exercise 3.2 in the book, just with different inputs — see the provided solution to 3.2a for guidance):
0#
01#01
01#010
The class of Turing-recognizable languages is closed under union. However, the following proof is not correct:
Consider language \(A\) that is recognized by a Turing machine \(M_A\), and language \(B\) that is recognized by Turing machine \(M_B\). We can create a TM \(M_C\) that recognizes \(C=A\cup B\) as follows: For a string \(x\), \(M_C\) first runs \(M_A\) on \(x\) — if \(M_A\) accepts, then \(M_C\) accepts \(x\) as a string in \(C\). Otherwise, \(M_C\) runs \(M_B\) on \(x\), and accepts or rejects depending on \(M_B\)’s result. Since \(M_C\) accepts \(x\) if and only if either \(M_A\) or \(M_B\) accept \(x\), \(M_C\) correctly recognizes the language \(C=A\cup B\).
What is wrong with this proof? (Be specific!)
Give a careful and complete description of how to modify a Turing machine \(M=(Q,\Sigma,\Gamma,\delta,q_0,q_{\mbox{accept}},q_{\mbox{reject}})\) to create a new TM \(M'\) that inserts a new symbol @ at the beginning of the tape, shifts the entire contents of input tape to the right one position, and then resets the head position to the position immediately after @ before starting TM \(M\).
Your description must be very specific about what states are created and what the transition function for \(M'\) is, using formal mathematical definitions. You should also illustrate your construction using a state diagram similar to those given in Figures 3.8 and 3.10, although you must indicate some parts as a “pattern” rather than showing every state and transition since the number of new states depends on the size of \(M\)’s tape alphabet \(\Gamma\).