Question $25$

The Venn diagram below shows several classes of languages. For each language $($a$)-($j$)$ in the list

below, indicate which classes it belongs to$,$ and which it doesn't belong to$,$ by dragging its

corresponding letter in the correct region of the diagram.

If a language does not belong to any of these classes, then place its letter above the top of the

diagram.

You may assume that, when Turing machines are encoded as strings, this is done using the Code$-$

Word Language $($CWL$),$ with input alphabet $\{a,b\}$ and tape alphabet $\{a,b,$#$,\}.$

$($a$)$ The empty language.

$($b$)$ The set of all strings in which a and b appear the same number of times.

$($c$)$ The set of all adjacency matrices of graphs. $($Such a matrix is represented as a string of in bits,

where $n$ is the number of vertices.$)$

$($d$)$ The set of adjacency matrices of $3-$colourable graphs.

$($e$)$ The set of all Boolean expressions that are not satisfiable.

$($f$)$ The set of all encodings of Turing machines.

$($g$)$ The set of all encodings of Turing machines that loop forever for all inputs.

$($h$)$ The set of strings of the form $x^n{y}^{2n}{z}^{3n},$ where $n$ is any positive integer.

$($i$)$ The set of legal positions in One$-$Dimensional Go$.$

$($j$)$ The set of illegal positions in One$-$Dimensional Go$.$