24 views

Let $L=\left\{s \overline{s_{R}} \mid s \in\{0,1\}^{*}\right\}$ be a language over alphabet $\{0,1\}$, where $\overline{s_{R}}$ describes the reverse complement of $s$. For an $s, \overline{s_{R}}$ is obtained by reversing the order of symbols in $s$ and then replacing every $0$ with $1$ and every $1$ with $0.$ As for example, if $s=1101$, the reverse order of $s$ is $1011$ and the reverse complement $\overline{s_{R}}$ is $0100.$

1. Give a context-free grammar which generates $L$.
2. Draw a Pushdown Automata that recognizes $L$.
3. Is $L$ a regular language? Justify your answer.