Deciding whether a CFG is parity absent

Question

Suppose that $\Sigma = \{c_1, \dots, c_m\}$ is some finite alphabet and supposing $s \in \Sigma^*$, let $\mathcal{I}_j(s)$ denote the number of instances of character $c_j$ in $s$. Call a string $s$ odd-parity absent iff $|\{j : \mathcal{I}_j(s) = 0\}|$ is odd. That is, $s$ is odd-parity absent iff an odd number of characters from the alphabet are missing from $s$. Call a language $L \subseteq \Sigma^*$ odd-parity absent iff every string in $L$ is odd-parity absent.

Now, suppose that $G$ is a CFG. I'd like to come up with an algorithm for deciding whether or not $L(G)$ is odd-parity absent.

I thought it'd make things simpler if we first convert $G$ into an equivalent Chomsky-normal form grammar. Now, If I could determine what types of terminal strings each variable yields in the grammar (e.g., variable $A$ yields strings with a's and strings with a's and b's, etc.) then I could just inspect the right-hand sides of the start variable rules. But $A$ of course can yield a whole bunch of different variables along the way to derive a string of terminals, and each of those variables can yield a whole other bunch of different variables along the way, etc.

Answer 1

One option to generate the parse tree of the grammar, and check all the leaf strings if they are odd-parity absent. Even if you have recursive rules, one application of each rule is enough, because multiple occurrences of the same element does not affect the result.

However, there might be an easier way. Consider the following grammar on {a,b,c,d,e} alphabet with the following rules:

• S -> A | B
• A -> Abc | C
• B -> cd | De
• C -> aa
• D -> b

Now you can assign odd-parity variables to each state. For example, a string at state S has number of missing instances = m (m=5 in this case). Let's denote it with p(S)=5.

From the first rule, p(A)=p(B)=p(S)=5. At the second rule, p(A) becomes 3, because at the first branch it eliminates 2 missing characters. Also p(C)=3, because p(A)=p(C), all other elements are missing.

At the third rule, p(B)=3 and p(D)=4. Fourth rule indicates p(C)=2 (2 a's, but the same element). Finally, p(D)=3.

Checking all ending states, p(B)=3, p(D)=3, and p(C)=2, which means the grammar has odd-parity. Verbally, there might be strings that end up with 3 elements missing, if they end up in state B or D.

In this way, you can decide if the grammar is odd-parity absent, just by looking at the grammar. The pseudo-code would be:

consumed_elements_set(S)={}
for each rule X with L as left-hand side:
    for each state R on the right hand side:
       consumed_elements_set(R)=consumed_elements_set(L)+terminals(X)
       p(R)=m-size(consumed_elements_set(R))
for each final state F:
    if p(F) is odd:
       print "not odd-parity absent!"