patternMinor
Proving $L = \{ w : w \neq w^R \}$ over $\Sigma = \{0,1\}$ is CFL
Viewed 0 times
provingcflneqsigmaover
Problem
I'm trying to prove $L = \{ w : w \neq w^R \}$ over $\Sigma = \{0,1\}$ is CFL.
Define $G = ({S,T}, \Sigma, R, S)$ where $R = S \to 0S0|1S1|0T1|1T0, \; T \to 0T|1T|\varepsilon$.
Now I want to show that $\mathcal{L}(G) = L$.
One direction is fine, where given $w\in \mathcal{L}(G)$, it must've deduced using $S \to 1T0|0T1$, and therefore $w \neq w^R$.
But given $w \in L$, all I know is $w \neq w^R$. How can I prove $w\in \mathcal{L}(G)$?
Define $G = ({S,T}, \Sigma, R, S)$ where $R = S \to 0S0|1S1|0T1|1T0, \; T \to 0T|1T|\varepsilon$.
Now I want to show that $\mathcal{L}(G) = L$.
One direction is fine, where given $w\in \mathcal{L}(G)$, it must've deduced using $S \to 1T0|0T1$, and therefore $w \neq w^R$.
But given $w \in L$, all I know is $w \neq w^R$. How can I prove $w\in \mathcal{L}(G)$?
Solution
Use induction.
For instance:
-
Define $\mathcal{L}_i(G) = \{ w \in \mathcal{L}(G) \mid |w| = i \}$ for $i \in \{ 0, 1, 2, \ldots \}$.
-
Prove that for all $w$ and $i > 1$, $w \in \mathcal{L}_i(G)$ if and only if $\exists x \in \Sigma, v \in \mathcal{L}_{i-2}(G) : xvx = w$.
For instance:
-
Define $\mathcal{L}_i(G) = \{ w \in \mathcal{L}(G) \mid |w| = i \}$ for $i \in \{ 0, 1, 2, \ldots \}$.
-
Prove that for all $w$ and $i > 1$, $w \in \mathcal{L}_i(G)$ if and only if $\exists x \in \Sigma, v \in \mathcal{L}_{i-2}(G) : xvx = w$.
Context
StackExchange Computer Science Q#85441, answer score: 5
Revisions (0)
No revisions yet.