4.
\\
\begin{center} Chomsky Hierarchy \\~\\
\resizebox{\textwidth}{!}{%
\begin{tabular}{|l|l|l|l|}
\hline
Grammar & Lanugage & Automaton & Production Rules \\ \hline
Type-3 & Regular & Finite State Automaton & $A \rightarrow a$ $\&$ $A$ $\rightarrow aB$\\ \hline
Type-2 & Context-Free & Push Down Automaton & $A \rightarrow \gamma$ \\ \hline
Type-1 & Context-Sensitive & Linear Bounded Automaton & $\alpha A \beta \rightarrow \alpha \gamma \beta$ \\ \hline
Type-0 & Recursively Enumerable & Turing Machine & $\alpha \rightarrow \beta$ \\ \hline
\end{tabular}%
}
\end{center}

$a$ = terminal \\
$\alpha$  = terminal, non-terminal, or empty \\
$\beta$  = terminal, non-terminal, or empty \\
$\gamma$  = terminal or non-terminal (never empty) \\
$A$ = non-terminal \\
$B$ = non-terminal \\~\\

The proof that this hierarchy is valid is simple and revolves around the production rules of each type being accomodative of the one below its type, but not above it.
\\~\\
The rules in Type-2, supersede Type-3 in the way that it doesn't restrict the right side of a production to be a single terminal or a terminal followed by a non-terminal or vice versa (right or left linear grammar), and allows more freedom in the body of its production being either a terminal or non-terminal, although not empty.
\\~\\
The rules in Type-1, can be seen as rules of a CFG (Type-2) where a variable A is replaced by a string $\beta$ in one step, with the only difference being that rule can be applied only in the context $\alpha_1$ \_\_ $\alpha_2$.
\\~\\
The rules in Type-0 are basically productions that are unrestricted in the sense that the head and the body allow variables, terminals, or empty productions without any context restriction as in the case of Type-1, hence supersede all the other types, thus making the Hierarchy valid.
\\~\\

6.  For a language L $\subseteq$  $\Sigma^*$, the characteristic function of L is represented by the function $\chi_L$ :  $\Sigma^* \rightarrow \{0, 1\}$ defined as --
\begin{equation*}
    \chi_L = \begin{cases}
               1               & x \in L\\
               0               & x \notin L\\
               \end{cases}
\end{equation*}
\\~\\

A Turing machine $T$ with input alphabet  $\Sigma$ accepts a language $L$ $\subseteq$  $\Sigma^*$ if $L(T ) = L$. $T$ decides $L$ if $T$ computes the characteristic function $\chi_L$ : $\Sigma^* \rightarrow \{0, 1\}$. \\
A language L is recursively enumerable if there is a TM that accepts L, and L is recursive if there is a TM that decides L.\\~\\

Suppose T is a TM that decides $L$ $\subseteq$  $\Sigma^*$. An algorithm to accept $L$ is the following: Given $x \in \Sigma^*$  , execute $T$ on input $x$. $T$ will halt and produce an output; if the output is 1 (i.e., if $\chi_L(x) = 1$), accept, and if the output is $0$, reject. \\~\\
i.e, If $L$ $\subseteq$  $\Sigma^*$ is accepted by a TM $T$ that halts on every input string, then L is recursive. Therefore, Every recursive language is recursively enumerable. Conversely, every recursively enumerable language need not be recursive. \\~\\

Given language $L = \{ \epsilon, 0,1,00,01,10,11,000,001...\}$, is basically $\Sigma^*$, $\Sigma = \{0,1\} \implies$ $L$ is regular. Therefore $L$ is recursive, hence it is also recursively enumerable. \\~\\

9. The decision problem of a CFG being ambiguous can be reduced to the Post Correspondence Problem, which is in itself an undecidable problem stated as follows - \\~\\

Let $A$ be an alphabet with at least two symbols.  The input of the problem consists of two finite lists $\alpha_{1}, \ldots, \alpha_{N}$ and $\beta_{1}, \ldots, \beta_{N}$ of words over $A$. A solution to this problem is a [[sequence]] of indices $(i_k)_{1 \le k \le K}$ with $K \ge 1$ and $ \le i_k \le N$ for all $k$, such that : $\alpha_{i_1} \ldots \alpha_{i_K} = \beta_{i_1} \ldots \beta_{i_K}.$ \\~\\

The most common proof for the undecidability of PCP describes an instance of PCP that can simulate the computation of an arbitrary Turing machine on a particular input. A match will occur if and only if the input would be accepted by the Turing machine. Because deciding if a Turing machine will accept an input is a basic undecidable problem, PCP cannot be decidable either. \\~\\

Consider an aribtrary PCP Instance: $w_1, . . . , w_k, x_1, . . . , x_k$ over $\Sigma$. (two words). Let $a_1$, . . . , $a_k$ be symbols not in $\Sigma$. \\~\\

Let $G$ be the CFG given by: \\
$S \rightarrow A \mid B$ \\
$A \rightarrow w_iAa_i \mid w_ia_i$ for $1 \leq i \leq k$ \\
$B \rightarrow x_iBa_i \mid x_ia_i$ for $1 \leq i \leq k$ \\~\\

where S, A, and B are distinct symbols not in $\Sigma \cup \{a_1, . . . , a_k\}$. If the instance of PCP has a solution, then G is clearly ambiguous. \\~\\

Suppose G is ambiguous, and let $z  \in (\Sigma \cup \{a_1, . . . , a_k\})^* ,\  \alpha, \beta, \gamma_1, \gamma_2 \in (\Sigma \cup \{a_1, . . . , a_k, S, A, B\})^*, \ and \ C \in \{S, A, B\}$ such that -- \\
1. S $\overset{*}{\implies} \alpha C \beta \implies \alpha \gamma_1 \beta \overset{*}{\implies} z$; \\
2. S $\overset{*}{\implies} \alpha C \beta \implies \alpha \gamma_2 \beta \overset{*}{\implies} z$; \\
3. $\gamma_1 \neq \gamma_2$ \\~\\

It is easily seen that there is at most one derivation A $\implies$ · · · $\implies$ z and at most one derivation B $\implies$ · · · $\implies$ z; hence $\alpha C \beta = S$. The string obtained by removing all $a_i$s from $z$ is a solution to the instance of PCP. The construction is clearly computable. Therefore, the ambiguity problem is undecidable. \\~\\

7.  A Turing Machine is coded and represented as a binary string such that the TM $M$ whose code is w\textsubscript{i} (the  i\textsuperscript{th} binary string). If M were the binary representation of TM and w were the  i\textsuperscript{th} binary string then the code of (M,w) will be TM string, followed by a separator followed by w. \\~\\
L\textsubscript{d} is a language that consists of the set of strings $w_i$ such that $w_i \notin L(M_i)$. \\~\\

An infinite table is constructed that describes the acceptance of each string to each Turing Machine. In this,  i\textsuperscript{th} row represents the i\textsuperscript{th} TM M\textsubscript{i}, where   j\textsuperscript{th} entry in the row is accepted (1) if M\textsubscript{i} accepts the   j\textsuperscript{th} word w\textsubscript{j}. \\~\\

Consider the language L\textsubscript{d} which is the language formed by taking the diagonal of this table. Formally, the word w\textsubscript{i} $\in$ L\textsubscript{d} iff M\textsubscript{i} accepts the string w\textsubscript{i}. Now, consider the complement language L= L\textsuperscript{c}, where c stands for the complement operation. \\~\\ The hypothesis is that this language $L_d$  cannot be recognized by any of the Turing Machine on the list.

We will prove the hypothesis using proof by contradiction. Let M\textsubscript{i} recognize the language L. Consider w\textsubscript{i}. There are two cases -- \\

\paragraph{1.} If M\textsubscript{i} accepts w\textsubscript{i} then the   i\textsuperscript{th} entry in the i\textsuperscript{th} row of this inifinite table is 1. Which implies in turn that w\textsubscript{i} $\notin$ L, but then M\textsubscript{i} (which recognizes L) must not accept w\textsubscript{i} $\implies$ Contradiction.

\paragraph{2.} If M\textsubscript{i} does not accept w\textsubscript{i} then the   i\textsuperscript{th} entry in the   i\textsuperscript{th} row of infinite table is 0 $\implies$ w\textsubscript{i} $\in$ L, but M\textsubscript{i} must accept w\textsubscript{i} $\implies$ Contradiction.\\~\\

Thus, it is L\textsubscript{d} is undecidable.