0
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ cs.stackexchange.com/q/18524/755 $\endgroup$
    – D.W.
    Feb 27 at 17:56
  • $\begingroup$ @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? $\endgroup$
    – Aishgadol
    Feb 27 at 18:06

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Aishgadol
    Feb 28 at 12:37
  • $\begingroup$ 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. $\endgroup$
    – Knogger
    Feb 28 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.