Are these two languages equivalent?

Question

$L = \{w \in \{a,b\}^{*}$ such that $w = R(w)\}$ R(w) = the reverse of w

$L = \{u \in \{a,b\}^{*}\}$

If not can you draw a pda or define a grammar for each?

I don't see how they could have different pdas or grammars.

Answer 1

The first language is the set of palindromes over $\{a, b\}$. The second language is the set of all strings over $\{a, b\}$. Clearly these are not the same language.

The grammar for $L_{palindrome}$ is:

$S \to \epsilon$

$S \to a$

$S \to b$

$S \to aSa$

$S \to bSb$

For the second language, there are only two states, both accepting. Both states transition to each other and loop to themselves. It's fairly easy to draw.