in Others edited by
24 views
0 votes
0 votes

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.
in Others edited by

Please log in or register to answer this question.

Related questions