3 Context-free languages (CFLs) For each $n \geq 1$, let $b(n) $ denote the binary representation of $n$, and let revb $(n)$ denote the reverse of $b(n)$. Some examples of these strings are provided for various values of $n$ in the following table: \begin{tabular}{[1|1|1|1|1|1|1|} \hline $\boldsymbol{n}$ in decimal & 5 & 6 & 12 & 13 & 43 & 44 \ \hline \hline$b(n)$ & 101 & 110 & 1100 & 1101 & 101011 & 101100 W \hline revb $(n) $ & 101 & 011 & 0011 & 1011 & 110101 & 001101 1 \hline \end{tabular) Consider the alphabet $\Sigma=\{0,1, . \}$, and define the language $L_{r} \subseteq \Sigma^{*}$ as follows: $$ L_{r}:=\{\operatorname[revb}(n) \cdot b(n+1) \mid n \geq 1 } $$ Based on the table above, the following strings are in $L_{r}$ : - $101.110$, for $n=5$; - $0011.1101$, for $n=12 ;$ $110101.101100$, for $n=43$. In fact, the first few elements of $L_{r}$ may be listed as: $$ L_{r}=\{1.10,01.11,11.100,001.101, \cdots } $$ Task 3.1. Show that $L_{r}$ is a context-free language by constructing a pushdown automaton (PDA) that accepts Lr. In particular, you are required to: (a) Provide a clear description of the main idea of the design of the PDA and what the stack is used for. This should not take more than half a page. (b) Draw a transition diagram for the constructed PDA. (10) cs. vs. 1241|