# Deciding if a language is CFL or in $P$

I'm trying to decide whether $$L_c=$${$$w=uxu, | \ u,x\in \Sigma ^* \ and \ |u|=c$$} for some constant $$c\in \mathbb{N}$$ is context free or not.

initialliy, I've thought about choosing $$x=\epsilon$$ which will lead to $$w=uu, \ u\in \Sigma ^*$$ but I've been told that since $$c$$ is a constant, it wont be the same language as $$L=$${$$uu | u\in \Sigma ^*$$} which put me in a standstill.

I've also thought about some examples that will make the pumping lemma not work on $$L_c$$, yet they all seem to fail (I couldent find a pumping constant that throws me out of $$L_c$$)

any ideas on how to progress from here?

• cs.stackexchange.com/q/18524/755
– D.W.
Feb 27 at 17:56
• @D.W. This is truely an eye opening post, however I couldent seem to find a 'technique' that fits the type of language I'm facing with, could you direct me to the part in cs.stackexchange.com/q/18524/755 that discusses these kind of languages? Feb 27 at 18:06

## 1 Answer

Observe that for some $$c \in \mathbb{N}$$ and finite alphabet $$\Sigma$$, $$\Sigma^c$$ with $$|\Sigma^c| = |\Sigma|^c$$ is finite. Therefore

$$L_c = \bigcup_{u \in \Sigma^c} u\Sigma^*u$$

is the union of a finite number of regular languages. So $$L_c$$ must be regular/context-free.

Assume that $$\Sigma$$ and $$c$$ are chosen as above and that $$\sim_c$$ is the indistinguishability relation for $$L_c$$. By the Myhill-Nerode theorem, $$L_c$$ is regular if and only if $$\Sigma^*/\sim_c$$ is finite. We now prove $$L_c$$ regular by showing that each string in $$\Sigma^*$$ is indistinguishable to one of length $$\leq 2c$$, so the number of classes in $$\Sigma^*/\sim_c$$ must be bounded by $$|\Sigma|^{2c}$$.

Choose $$w \in \Sigma^*$$, if $$|w| \leq c$$ then $$w \sim_c w$$. If $$|w| > c$$ then there must be $$u \in \Sigma^c$$, $$y \in \Sigma^+$$ such that $$w = uy$$. Now take the greatest prefix $$u_1$$ of $$u$$ such that $$y = xu_1$$ for some $$x \in \Sigma^*$$. If $$z \in \Sigma^*$$ with $$|z| \geq c$$, then

$$wz = uyz \in L_c \iff u \text{ is a suffix of } z \iff uu_1z \in L_c.$$

Because $$u_1$$ is the greatest prefix of $$u$$ with $$w = uxu_1$$, it follows that if $$|z| < c$$ then also

$$wz = uyz \in L_c \iff u_2z = u \text{ for a suffix } u_2 \text{ of } u_1 \iff uu_1z \in L.$$

So $$w \sim_c uu_1$$ and $$|uu_1| \leq |uu| = 2c$$, done.

• this is interesting, I've proven that $L_c$ is not regular using the Myhill-Nerode theorm, I choose {$0^cx0^i$}$_{i=0}^{\infty}$ for some $c\in \mathbb{N}$ and $x\in \Sigma ^*$. and by choosing $z=0^{c-i}$ shown there are infinite equivalence classes which is a contradiction to the theorm, however I am unsure on how to show that it is context free, could you elaborate more on your solution? Feb 28 at 12:37
• Sorry, I don't really understand how you get an infinite number of equivalence classes here 😅 I've also added a proof of the regularity of $L_c$ using the the Myhill-Nerode theorem to my answer. Feb 28 at 14:40