Is $M(L)=\left\{w \in L \mid \forall v \in \Sigma^+,vw \notin L\right\}$context-free?

187 Views Asked by At

$L$ is a context-free language.

We define $M\left(L\right)=\left\{w \in L \mid \forall v \in \Sigma^+,vw \notin L\right\}$ .

It seems like $M\left(L\right)$ is the set of strings in $L$ which are not the suffix of other strings in $L$.

I've tried to solve it by using the CFG but failed. Can anyone gives some tips please?

1

There are 1 best solutions below

0
On

I think $M\left(L\right)$ is not necessarily a context-free language, and I have found a counterexample for my homework this week:

$$L:=\left\{0^{i}1^{j}2^{k}\mid i,j,k\in\mathbb{N}^{+},i=j\lor j\neq k\right\}$$

where its corresponding $M\left(L\right)$ can be verified to be:

$$M\left(L\right) = \left\{0^{n}1^{n}2^{n}\mid n\in\mathbb{N}^{+}\right\}$$

which is obviously not context-free.

Are you also in the class of 2023(Fall)FLA@NJU? If so(or you are also doing your homework), please give a citation of this tips for the need of Academic Integrity.