Theorem 1

Theorem: Let \(S\) be an infinite countable set. Its powerset \(2^S\) is not countable.

Proof: Use diagonalization

\[\begin{split}\begin{array}{c|cccccccc} & s_1 & s_2 & s_3 & s_4 & s_5 & s_6 & s_7 & ... \\ \hline t_1 & \underline{0} & 1 & 0 & 1 & 0 & 0 & 1 & ... \\ t_2 & 1 & \underline{1} & 0 & 0 & 1 & 1 & 0 & ... \\ t_3 & 0 & 0 & \underline{0} & 0 & 1 & 0 & 0 & ... \\ t_4 & 1 & 0 & 1 & \underline{0} & 1 & 1 & 0 & ... \\ t_5 & 1 & 1 & 1 & 1 & \underline{1} & 1 & 1 & ... \\ t_6 & 1 & 0 & 0 & 1 & 0 & \underline{0} & 1 & ... \\ t_7 & 0 & 1 & 0 & 1 & 0 & 0 & \underline{0} & ... \\ ... & \\ \\ \hline \hline \hat{t} & 1 & 0 & 1 & 1 & 0 & 1 & 1 & ...\\ \end{array}\end{split}\]

Theorem 2

Theorem: For any nonempty \(\Sigma\), there exist languages that are not recursively enumerable.

Proof:

Theorem 3

Theorem: There exists a recursively enumerable language \(L\) such that \(\bar L\) is not recursively enumerable.

Proof:

Theorem 4

Theorem: If languages \(L\) and \(\bar{L}\) are both RE, then L is recursive.

Proof:

Theorem 5

Theorem: If \(L\) is recursive, then \(\bar{L}\) is recursive.

Proof:

Example 1

Let \(G = (\{S,A,X\}, \{a,b\},S,P), P =\)

\(S \rightarrow bAaaX\)

\(bAa \rightarrow abA\)

\(AX \rightarrow \lambda\)

A derivation of \(aab\) is: (the left hand side that is replaced is underlined)

\(S \Rightarrow \underline{bAa}aX \Rightarrow a\underline{bAa}X \Rightarrow aab\underline{AX} \Rightarrow aab\)

Example 2

Find an unrestricted grammar \(G\) such that \(L(G) = \{a^nb^nc^n | n> 0\}\)

\(G = (V,T,S,P)\)

\(V = \{S,A,B,D,E,X\}\)

\(T = \{a,b,c\}\)

\(P =\)

Change the last rule to \(DX \rightarrow c\) and you can derive the string \(aaabbcbcc\), moves a \(c\) in the wrong place to the end of the string…

To derive string \(aaabbbccc\), use productions 1, 2 and 3 to generate a string that has the correct number of a’s b’s and c’s. The a’s will all be together, but the b’s and c’s will be intertwined.

\(S \Rightarrow AX \Rightarrow aAbcX \Rightarrow aaAbcbcX \Rightarrow aaaBbcbcbcX\)

Use a \(B\) to move right through a group of \(B\) ‘s until it sees a \(c\). Replace the \(c\) by a \(D\), and use the \(D\) to move right to the end of the string. Then write the \(c\) at the end of the string. Use an \(E\) to move back to the left.

\(aaaBbcbcbcX \Rightarrow aaabBcbcbcX \Rightarrow aaabDbcbcX\)

\(\Rightarrow aaabbDcbcX \Rightarrow aaabbcDbcX \Rightarrow aaabbcbDcX\)

\(\Rightarrow aaabbcbcDX \Rightarrow aaabbcbcEXc\)

\(\Rightarrow aaabbcbEcXc\)

\(\stackrel{*}{\Rightarrow} aaaEbbcbcXc \Rightarrow aaaBbbcbcXc\)

Repeat this process until all the \(c\) ‘s have been moved to the end of the string. Then remove the \(X\) from the string.

\(aaaBbbcbcXc \stackrel{*}{\Rightarrow} aaaBbbbXccc \stackrel{*}{\Rightarrow} aaabbbBXccc \Rightarrow aaabbbccc\)

Theorem 6

Theorem: If \(G\) is an unrestricted grammar, then \(L(G)\) is recursively enumerable.

Proof:

• List all strings that can be derived in one step.

  \(S \Rightarrow w\)

• List all strings that can be derived in two steps.

  \(S \Rightarrow x \Rightarrow w\)

• List all strings that can be derived in three steps.

• Continue in this way for strings deriveable in any finite number of steps.

• Therefore, it is possible to enumerate all strings in the language.

Theorem 7

Theorem: If \(L\) is recursively enumerable, then there exists an unrestricted grammar \(G\) such that \(L = L(G)\).

Proof: (Sketch!)

L is recursively enumerable.

\(\Rightarrow\) there exists a TM \(M\) such that \(L(M) = L\).

\(M = (Q, \Sigma, \Gamma, \delta, q_0, B, F)\)

Idea \(M\) starts with \(w\) and eventually ends up with a final state.

\(q_0w \stackrel{*}{\vdash} x_1q_fx_2\) for some \(q_f \in F, x_1, x_2 \in \Gamma^*\)

Construct an unrestricted grammar \(G\) such that \(L(G) = L(M)\).

But in \(G\), grammar starts with \(S\) and eventually derives \(w\), \(S \stackrel{*}{\Rightarrow}w\)

So the constructed grammar will mimic the Turing machine in reverse.

Three steps:

1. \(S \stackrel{*}{\Rightarrow} B \ldots B\#xq_fyB\ldots B\)

with \(x, y \in \Gamma^*\) for every possible combination

2. \(B \ldots B\#xq_fyB\ldots B \stackrel{*}{\Rightarrow} B\ldots B\#q_0wB\ldots B\)

by following rules that mimic transitions in reverse order.

3. \(B\ldots B\#q_0wB\ldots B \stackrel{*}{\Rightarrow} w\)

Here just remove the blanks, and \(\# q_0\).

So here is the constructed grammar.

\(G = (V,T,S,P)\)

\(T = \Sigma\)

\(V = \{\Gamma - \Sigma\} \cup Q \{\#\} \cup \{S,A\}\)

\(P\) for each of the three above are:

1. For \(S\stackrel{*}{\Rightarrow}B\ldots B\#xq_fyB\ldots B\)

\(S \rightarrow BS \mid SB \mid \#A\)

Replace \(S\) with lots of blanks and then finally a #`

\(A \rightarrow aA \mid Aa \mid q\)

(for every \(a \in \Gamma\) and \(q \in F\))

then generate the strings of symbols finishing off with a final state.

2. For \(B\ldots B\# xq_fyB\ldots B \stackrel{*}{\Rightarrow} B\ldots B\# q_0wB\ldots B\)

Create the rules that mimic what the TM does in reverse order.

Mimic left and right moves.

For each \(\delta(q_i,a) = (q_j,b,R)\)

Add to \(P\), \(bq_j \rightarrow q_ia\)

For each \(\delta(q_i,a)=(q_j,b,L)\)

add to \(P\), \(q_jcb \rightarrow cq_ia\) for every

\(c \in \Gamma\).

3. For \(B\ldots B\# q_0wB\ldots B \stackrel{*}{\Rightarrow} w\)

To get rid of \(\# q_0\) and blanks,

\(\# q_0 \rightarrow \lambda\)

\(B \rightarrow \lambda\)

Then show that \(S \stackrel{*}{\Rightarrow} w\) iff \(q_0w \stackrel{*}{\vdash} x_1q_fx_2\) for \(q_f \in F\)