4
$\begingroup$

$ALLEVEN_{CFG}$ = {M is a grammar, and L(M) includes all strings of even length in $\Sigma^*$} = {(M): ($\Sigma\Sigma$)* ⊆ L(M)}

$ALLODD_{CFG}$ = {M is a grammar, and L(M) includes all strings of odd length in $\Sigma^*$} = {(M): $\Sigma$($\Sigma\Sigma$)* ⊆ L(M)}

Is $ALLEVEN_{CFG} \cap ALLODD_{CFG}$ Turing Decidable?

I thought that this was yes because ALLEVEN would produce strings that are only even in length. ALLODD would produce strings that are only odd in length. The intersection would then be producing strings that are both even and odd in length, which is nothing. This means that we can reduce the problem to $E_{CFG}$ which is a decidable.

However, my professor says that $ALLEVEN_{CFG} \cap ALLODD_{CFG}$ is exactly $ALL_{CFG}$ which is not decidable. I am not sure how he reached the conclusion that it is equal to $ALL_{CFG}$.

$\endgroup$
  • 1
    $\begingroup$ The condition is on $M$, you are incorrectly applying to the strings thereby concluding that since a string cannot be both even and odd at the same time the only accepted languages are $\phi$. $\endgroup$ – Shreesh Mar 24 '16 at 7:15
  • 1
    $\begingroup$ I think you mean G instead of M, usually M stands for Turing Machines. It is just a convention, nothing really wrong saying M is a grammar. $\endgroup$ – Shreesh Mar 24 '16 at 8:25
8
$\begingroup$

The problem is that you interpret e.g. "grammars that generate all even length strings" as "grammars that generate only all even length strings", which is wrong. If you look at it this way, the intersection you are looking for is grammars that generate all even length strings and all odd length strings, i.e., grammars that generate all of $\Sigma^*$

$\endgroup$
1
$\begingroup$

$ALLEVEN_{CFG} \cap ALLODD_{CFG} = \{G$ is a CFG grammar $\mid\ L(G)$ includes all strings of odd length and even length in $\Sigma^* \}$. This is because a $G$ that belongs to both sets will have to satisfy the conditions of both the sets.

which really means

$ALLEVEN_{CFG} \cap ALLODD_{CFG} = \{G$ is a CFG grammar $ \mid\ L(G)$ is $\Sigma^* \}$.

If your teacher means $ALL_{CFG}$ to be $\{G$ is a CFG grammar $\mid\ L(G)$ is $\Sigma^* \}$ then he is correct.

The set $ALL_{CFG}$ is definitely undecidable, refer undecidable problems related to CFG.

$\endgroup$
  • $\begingroup$ Teacher might be using a different pronoun. $\endgroup$ – Yuval Filmus Mar 24 '16 at 12:00
1
$\begingroup$

I am not sure how he reached the conclusion that it is equal to $\mathrm{ALL}_{\mathrm{CFG}}$.

By simple logic. You have two languages defined by predicates like so:

$\qquad G_P = \{ \text{CFG } G \mid \forall\, w \in \Sigma^*.\ P(w) \implies w \in L(G) \}$.

Then,

$\qquad\begin{align*} G_P \cap G_Q &= \{ \text{CFG } G \mid \bigl[ \forall\, w \in \Sigma^*.\ P(w) \implies w \in L(G) \bigr] \\ &\hspace{2.5cm}\land \bigl[ \forall\, w \in \Sigma^*.\ Q(w) \implies w \in L(G) \bigr] \} \\ &= \{ \text{CFG } G \mid \forall\, w \in \Sigma^*.\ P(w) \lor Q(w) \implies w \in L(G) \}. \end{align*}$

Since in your case $P$ is "has even length" and $Q$ "has odd length", and every word has either even or odd length, every $G$ in the specified set has to contain all words.

$\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.