I need to determine whether $L$ is regular or at least context-free. $$L = \{ xwx : x,w \in \{a,b,c \}^*, |x| > 0\}$$ My initial guess is that it is regular.
I think that $L$ is context free. I have come up with a simple grammar, yet I am not sure if that's the way to go:
$$S \rightarrow a\text{Any}a | b\text{Any}b | c\text{Any}c $$ $$Any \rightarrow a | b | c | aAnya |aAnyb|aAnyc|bAnya | \ldots |\epsilon$$
Is it a potentialyl good grammar?
$L$ is not context free (and in fact, the version of $L$ with only two symbols is also not context free).
To show this, I will use the generalized condition under the Wikipedia page for Ogden's lemma with $e = 3$ and $d = 16p + 5 \ge p(e+1)$, and apply it to the word $a^{4p+2} b^{4p+2} a^{4p+2} b^{4p+2}$ with excluded positions being the start of the 2nd, 3rd, and 4th blocks and all other positions being distinguished. Now, the excluded positions will ensure that each of $v, x$ stays within one of the blocks, while the condition that $vwx$ has at most $p(e+1) = 4p$ distinguished positions ensures that $v$ and $x$ are either in the same block or in adjacent blocks. It now remains to check in each case that either $u v^0 w x^0 y$ or $u v^2 w x^2 y$ is not in $L$, giving a contradiction. (It will be useful in each case to use the observation that if $k_1, k_4 > 0$, then $a^{k_1} b^{k_2} a^{k_3} b^{k_4} \in L$ if and only if $k_3 \ge k_1$ and $k_2 \ge k_4$.)
To illustrate one of these cases, let us suppose that $v = b^k$ from the second block and $x = a^\ell$ from the third block. Then $u v^0 w x^0 y = a^{4p+2} b^{4p+2 - k} a^{4p+2-\ell} b^{4p+2} \notin L$ by the above observation, since $vx$ cannot be empty so either $k > 0$ or $\ell > 0$.