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 $Ato a$ mark $A$ as “odd”
Repeat as long as variables get new marks:
- For $Ato 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
