1
$\begingroup$

Given a context-free grammar, is there an algorithm to determine if the CFG will ever produce an even length string? Or is this undecidable?

$\endgroup$
0

3 Answers 3

1
$\begingroup$

Of course there is a meta-algorithm via automata and intersection constructions. Here is an algorithm that works out of the box, no tools needed.

We mark any variable in the grammar as "even" and/or "odd". Variables can have either no, one or zero marks. For simplicity we assume the grammar is in Chomsky normal form, but the trick can be reformulated for general grammars.

  • For any $A\to a$ mark $A$ as "odd"

Repeat as long as variables get new marks:

  • For $A\to BC$, if $B$ and $C$ are marked, carry the mark over to $A$ according to parity ("odd"+"odd"="even", etc.)

Yes, I know that is an implementation of "CFG emptiness" and "intersection with even length strings" merged, but still I like it.

$\endgroup$
1
  • $\begingroup$ Then, I would determine if the grammar produces an even string if S is ever marked even. Because a variable can be marked as both even or odd at different times. $\endgroup$
    – ASDF
    Feb 6, 2014 at 22:28
2
$\begingroup$

There is an algorithm:

Recall that given a CFL $L$ and a regular language $K$, the language $L\cap K$ is also CFL (and a CFG for it is computable given a CFG for $L$ and a DFA for $K$).

Now, observe that the language $K=\{w: |w| \text{ is even}\}$ is regular.

From this we conclude that given a CFG $G$, we can construct a CFG for the language $\{w: |w|\text{ is even and }w\in L(G)\}$, and we observe that this language is nonempty iff $G$ generates a word of even length.

Since checking emptiness of CFG can be done in polynomial time, we can solve the problem in polynomial time.

$\endgroup$
2
  • $\begingroup$ Regarding polynomial total time, it should be noted that intersecting $L$ and $K$ is also possible in that time. Do we need a DFA for that step? $\endgroup$
    – Raphael
    Feb 6, 2014 at 21:20
  • $\begingroup$ Note that $K$ here is constant, so we don't really need the DFA, as the construction is fixed. We also don't really need the fact that the runtime is polynomial, but rather that is is polynomial in $L$. Thanks. $\endgroup$
    – Shaull
    Feb 7, 2014 at 6:04
2
$\begingroup$
  1. The language of all even-length strings is regular, and you can construct a DFA that recognizes it.
  2. The intersection of a regular language and a context-free language is context-free, and you can construct a CFG for it.
  3. Given a CFG, it's decidable whether the language it generates is empty.
  4. The language from (2) is empty as in (3) iff your context-free language generates no even-length strings.

See this for details.

$\endgroup$

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