[Solved]: Is the set of CFGs that contain all odd and even length words Turing-decidable?

Problem Detail: 

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

Asked By : user3370201

Answered By : vonbrand

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54876

 Ask a Question

 Download Related Notes/Documents