1
$\begingroup$

I want to prove that the following language is decidable:

$$\mathit{SEQ}_{\mathit{CFG}} = \{⟨G⟩ \mid \text{$G$ is CFG and $L(G) ⊈ L$}\}, \text{ where } L = \Sigma^* - \{\epsilon\}$$

So, I think about the relationship between equality and substrings.

for example, I saw in different questions that when we have $L(G) = L(H)$ we can perform that proof on the $L(G) ⊆ L(H)$.

So can I do that with $L(G) ⊈ L$?

So what is the benefit of saying $L = \Sigma^* - {\epsilon}$ ? I'm a bit confused. Can anyone help me with this question?

$\endgroup$
1
$\begingroup$

The idea is that $L(G) \not\subseteq \Sigma^* \setminus \{\epsilon\}$ iff $\epsilon \in L(G)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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