Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
1  
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$. – Shreesh Mar 24 at 7:15
1  
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. – Shreesh Mar 24 at 8:25
up vote 8 down vote accepted

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^*$

share|cite|improve this answer

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

share|cite|improve this answer
    
Teacher might be using a different pronoun. – Yuval Filmus Mar 24 at 12:00

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.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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