1
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ It is decidable for a context-free grammar $G$ and a regular language $R$ whether $L(G) \subseteq R$. $\endgroup$ – Hendrik Jan Jan 31 '17 at 10:05
-1
$\begingroup$

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!"
$\endgroup$
  • $\begingroup$ Be careful. The set of letters derived from a variable is not a single value in general, as you show in your own example for $A$ (which may either derive $\{a\}$ or $\{a,b,c\}$. This might result in variables that are both odd and even at the same time. $\endgroup$ – Hendrik Jan Jan 31 '17 at 12:45
  • $\begingroup$ 1. What is the parse tree of a grammar? I know what the parse tree of a word in the language is, but I'm not familiar with the notion of a parse tree of the grammar. Can you explain? 2. I don't think this procedure works. Consider the rule B -> Cab, where we know p(B)=3. Can we say that p(C)=1? No, because we don't know whether the two characters that were missing from B include a,b or not. $\endgroup$ – D.W. Jan 31 '17 at 22:18
  • $\begingroup$ 3. I don't see why you say that one application of each rule is enough. Consider the rule A -> BAC, where B -> D | E. Why is one application of the first rule enough? It seems like we might need two applications of the first rule, one application where we later use B -> D and another application where we later use B -> E. $\endgroup$ – D.W. Jan 31 '17 at 22:18
  • $\begingroup$ 1. Parse tree of the grammar is the tree that shows strings from all possible non-repeating rule applications. 2. Look at the pseudo-code, that's why consumed_elements are stored instead of $p(i)$s. 3. "for each rule", as B->D and B->E are separable rules, and "for each state on the right hand side" covering the iteration on the rule $A->BAC$ per RHS non terminal. $\endgroup$ – ilke444 Jan 31 '17 at 23:45

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.