Determining if a context-free grammar produces even-length strings

Problem Detail: 

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?

Asked By : ASDF

Answered By : Hendrik Jan

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.

Best Answer from StackOverflow

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