91Ó°ÊÓ

Let$MAX-CLIQUE=\left\{\right(G,k\left)\right|alargestcliqueinGisofsizeexactlyk\}$. Use the result of Problem 7.47 to show that MAX-CLIQUEis DP-complete.

If $\mathbf{A}$has$\mathbf{a}$ elements and$\mathbf{B}$ has$\mathbf{b}$ elements, how many elements are in$\mathbf{A}\mathbf{×}\mathbf{B}$? Explain your answer.

Question: Each of the following languages is the intersection of two simpler languages. In each part, construct DFAs for the simpler languages, then combine them using the construction discussed in footnote 3 (page 46) to give the state diagram of a DFA for the language given. In all parts,$∑=a,b$.

$$\begin{gathered} \mathbf{\text{a.}}\mathbf{\left\{}\mathbf{w}\mathbf{|}\mathbf{w}\mathbf{\backslash }\mathbf{kern}\mathbf{1}\mathbf{pt}\mathbf{ }\mathbf{\text{has}}\mathbf{ }\mathbf{ }\mathbf{\text{at}}\mathbf{ }\mathbf{ }\mathbf{\text{least}}\mathbf{ }\mathbf{ }\mathbf{\text{three}}\mathbf{ }\mathbf{ }\mathbf{a}\mathbf{\text{'}}\mathbf{\text{s}}\mathbf{ }\mathbf{ }\mathbf{\text{and}}\mathbf{ }\mathbf{ }\mathbf{\text{at}}\mathbf{ }\mathbf{ }\mathbf{\text{least}}\mathbf{ }\mathbf{ }\mathbf{\text{two}}\mathbf{ }\mathbf{ }\mathbf{b}\mathbf{\text{'}}\mathbf{\text{s}}\mathbf{\right\}}\mathbf{}\mathbf{}\mathbf{} \\ \mathbf{\text{b.}}\mathit{w}\mathbf{|}\mathit{w}\mathbf{\backslash }\mathit{k}\mathit{e}\mathit{r}\mathit{n}\mathbf{1}\mathit{p}\mathit{t}\mathbf{ }\mathbf{\text{has}}\mathbf{ }\mathbf{ }\mathbf{\text{exactly}}\mathbf{ }\mathbf{ }\mathbf{\text{two}}\mathbf{ }\mathbf{ }\mathit{a}\mathbf{\text{'}}\mathbf{\text{s}}\mathbf{ }\mathbf{ }\mathbf{\text{and}}\mathbf{ }\mathbf{ }\mathbf{\text{at}}\mathbf{ }\mathbf{ }\mathbf{\text{least}}\mathbf{ }\mathbf{ }\mathbf{\text{two}}\mathbf{ }\mathbf{ }\mathit{b}\mathbf{\text{'}}\mathbf{\text{s}} \\ \mathbf{\text{c.}}\mathit{w}\mathbf{|}\mathit{w}\mathbf{\backslash }\mathit{k}\mathit{e}\mathit{r}\mathit{n}\mathbf{1}\mathit{p}\mathit{t}\mathbf{ }\mathbf{\text{has}}\mathbf{ }\mathbf{ }\mathbf{\text{even number}}\mathbf{ }\mathbf{ }\mathbf{\text{of}}\mathbf{ }\mathbf{ }\mathit{a}\mathbf{\text{'}}\mathbf{\text{s}}\mathbf{ }\mathbf{ }\mathbf{\text{and}}\mathbf{ }\mathbf{ }\mathbf{\text{one or}}\mathbf{ }\mathbf{ }\mathbf{\text{two}}\mathbf{ }\mathbf{ }\mathit{b}\mathbf{\text{'}}\mathbf{\text{s}} \\ \mathbf{\text{d.}}\mathbf{\left\{}\mathbf{w}\mathbf{|}\mathbf{w}\mathbf{\backslash }\mathbf{kern}\mathbf{1}\mathbf{pt}\mathbf{ }\mathbf{\text{has}}\mathbf{ }\mathbf{ }\mathbf{\text{even number}}\mathbf{ }\mathbf{ }\mathbf{\text{of}}\mathbf{ }\mathbf{ }\mathbf{a}\mathbf{\text{'}}\mathbf{\text{s}}\mathbf{ }\mathbf{ }\mathbf{\text{and each}}\mathbf{a}\mathbf{\text{is followed by at least}}\mathbf{ }\mathbf{ }\mathbf{\text{one}}\mathbf{ }\mathbf{b}\mathbf{\right\}} \\ \mathbf{\text{e.}}\mathit{w}\mathbf{|}\mathit{w}\mathbf{\backslash }\mathit{k}\mathit{e}\mathit{r}\mathit{n}\mathbf{1}\mathit{p}\mathit{t}\mathbf{ }\mathbf{\text{starts}}\mathbf{ }\mathbf{ }\mathbf{\text{with}}\mathbf{ }\mathbf{ }\mathbf{\text{an}}\mathbf{ }\mathbf{ }\mathit{a}\mathbf{ }\mathbf{ }\mathbf{\text{and}}\mathbf{ }\mathbf{ }\mathbf{\text{has at most one}}\mathbf{ }\mathbf{ }\mathit{b} \\ \mathbf{\text{f.}}\mathit{w}\mathbf{|}\mathit{w}\mathbf{\backslash }\mathit{k}\mathit{e}\mathit{r}\mathit{n}\mathbf{1}\mathit{p}\mathit{t}\mathbf{ }\mathbf{\text{has an odd number of}}\mathit{a}\mathbf{\text{'}}\mathbf{\text{s}}\mathbf{ }\mathbf{ }\mathbf{\text{and ends with a}}\mathbf{ }\mathbf{ }\mathit{b} \\ \mathbf{\text{g.}}\mathit{w}\mathbf{|}\mathit{w}\mathbf{\backslash }\mathit{k}\mathit{e}\mathit{r}\mathit{n}\mathbf{1}\mathit{p}\mathit{t}\mathbf{ }\mathbf{\text{has even length and an odd number of}}\mathit{a}\mathbf{\text{'}}\mathbf{\text{s}}\mathbf{} \end{gathered}$$

Give a formal definition of an enumerator. Consider it to be a type of two-tape Turing machine that uses its second tape as the printer. Include a definition of the enumerated language

Let$\mathit{x}\mathit{a}\mathit{n}\mathit{d}\mathit{y}$ be strings and let L be any language. We say that x and y are distinguishable by L if some string Z exists whereby exactly one of the strings$\mathit{x}\mathit{z}\mathit{a}\mathit{n}\mathit{d}\mathit{y}\mathit{z}$ is a member of L ; otherwise, for every string z , we have $\mathbf{xz}\mathbf{∈}\mathit{L}$whenever $\mathit{y}\mathit{z}\mathbf{∈}\mathit{L}$and we say that are indistinguishable by L. If $xandy$are indistinguishable by L, we write x ≡L y. Show that$\mathbf{≡}\mathit{L}$is an equivalence relation.

Show that P is closed under homomorphism iff P = NP.

Myhill–Nerode theorem. Refer to Problem $\mathbf{1}.\mathbf{51}$ . Let L be a language and let X be a set of strings. Say that X is pairwise distinguishable by L if every two distinct strings in X are distinguishable by L. Define the index of L to be the maximum number of elements in any set that is pair wise distinguishable by L . The index of L may be finite or infinite.

a. Show that if L is recognized by a DFA with k states, L has index at most k.

b. Show that if the index of L is a finite number K , it is recognized by a DFA with k states.

c. Conclude that L is regular iff it has finite index. Moreover, its index is the size of the smallest DFA recognizing it.

Let G₁ be the following grammar that we introduced in Example

2.45. Use the DK-test to show that G₁is not a DFG.
$R→S|T$

$S→aSb|ab$

$T→aTbb|abb$

Let $\mathit{A}\mathbf{=}\mathit{L}\left(G_1\right)$where is defined in Problem 2.55. Show that A is not a DCFL. (Hint: Assume that A is a DCFL and consider its DPDA P . Modify P so that its input alphabet is $\left\{a,b,c\right\}$. When it first enters an accept state, it pretends that c's are b's in the input from that point on. What language would the modified P accept?)

If we disallow $\mathrm{Î\mu }-$ in CFGs, we can simplify the $DK$-test. In the simplified test, we only need to check that each of $DK$’s accept states has a single rule. Prove that a CFG without $\mathrm{Î\mu }-$ passes the simplified $DK$-testiff it is a DCFG.