$($a$)$ How could you encode Boolean expressions in CNF over our alphabet $\{a,b\}?$

Assume that the variables in the expression are $x_1,x_2,$dots,$x_n,$ and that each of

these variables occurs in at least one literal in the expression.

Your encoding scheme should be such that each Boolean expression in CNF$,$ us$-$

ing these variables, can be encoded and different expressions are encoded differently.

Subject to this, it should be reasonably efficient, i$.$e$.,$ not produce strings that are

unduly long.

Let $3$CNF be the language of $($string representations of$)$ Boolean expressions in

CNF with exactly three literals in each clause and with no literals duplicated in any

clause and no clauses duplicated.

$($b$)$ Give the best upper bound you can for the length of the string used, in your

scheme, for Boolean expressions in $3$CNF with $m$ clauses and $n$ variables.

$($c$)$ Outline how a Turing machine would recognise $3$CNF$.$

$($d$)$ In terms of $m$ and $n,$ how many steps would a Turing machine need to take, in

the worst case, to decide if an input string belongs to $3$CNF$?$

$($e$)$ Now give a time bound in terms of the number $l$ of letters in the input string,

in big$-$O notation.

$($f$)$ How would you classify $3$ CNF $,$ using language classes we have studied? Is it

finite, regular, context$-$free, decidable, $...?$ Justify your answer.