1
$\begingroup$

Let $L$ be the language$\{\langle G \rangle : G\text{ is a CFG and L(G) accepts at least one odd-length strings}\}$.

Prove that $L$ is decidable or undecidable.

Here is my attempt:

$L$ = On input $\langle G \rangle$, where $\langle G \rangle$ is a CFG:

  1. Construct CFG, such that $L(O)$ contains only odd length strings.
  2. Construct CFG $\langle H \rangle$ such that $L(H) = L(O) \cap L(G)$
  3. Input $\langle H \rangle$ to the decider $E_{\text{cfg}}$
  4. If it accepts, $reject$.
  5. Else, $accept$.

Is my proof correct? In the first step, can I construct a DFA, $O$ such that $L(O)$ consists of only odd length strings instead of a CFG?

$\endgroup$
3
$\begingroup$

You cannot compute the intersection of two context-free grammars, at least not if you expect the answer to be another context-free grammar. The reason is that context-free languages are not closed under intersection (consider $a^nb^nc^m \cap a^mb^nc^n = a^nb^nc^n$).

However, context-free languages are closed under intersection with a regular language, and moreover there is an efficient algorithm that, given a context-free grammar $G$ and an NFA $A$, computes a new context-free grammar for the language $L(G) \cap L(A)$. You should use this algorithm in your second step.

Another problem with your solution is that it's not clear what you mean by "$L(O)$ contains only odd length strings". There are many languages that contain only odd length strings, for example the empty language. You want $L(O)$ to contain only and all odd length strings, that is, you want it to be the language of odd length strings.

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