Determine if this language is context-free

77 Views Asked by At

Let $$L_1=\{W_1@W_2 \mid \exists k \text{ such that } |W_1|>|W_2|\ge k, W_1[k]=W_2[k],\Sigma =\{0,1\}\}$$ where $k$ is an arbitrary number and $W_i[k]$ means the $k$-th character in $W_i$.
So this is the language and I want to know if it is context-free or not.
I've tried to write a grammar for this language, based on another one that I've written:
$$L_2=\{W_1@W_2 \mid \exists k \text{ such that } |W_1|,|W_2|\ge k,W_1[k]=W_2[k],\Sigma =\{0,1\}\}$$ And the grammar is: (The $S$ is the starting variable)
$S\to A1X \mid B0X$
$X\to LX \mid L$
$L\to 0 \mid 1$
$A\to LAL\mid 1X@$
$B\to LBL \mid 0X@$
But every grammar I wrote had some flaws. If you want I can write my latest grammar and its flaw.
Sorry for my bad English, I'm not native :)
Thank you in advance for your help.