I am trying to prove that $$\{u\#v\,|\,u,v\in\{0,1\}^∗ \text{and }u \text{ is a substring of }v\}$$ is not context free. Is it possible for a subset of a non-context free language to be context-free?
Asked
Active
Viewed 31 times
0
-
Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to. – José Carlos Santos Feb 18 '20 at 09:21
-
Is it possible for a subset of a non-context free language to be context-free? Yes: take the empty subset of any non-context free language. – J.-E. Pin Feb 18 '20 at 10:43