Here’s another kind of grammar I hadn’t heard of until doing these problems.

**The problem: **Context-Free Programmed Language Membership. This is problem AL17 in the appendix.

**The description: **Given an ε-free Context-Free programmed grammar (explained below) G, and a string x, is x in the language generated by G?

**Example: **A programmed grammar gives a label to each production, and then after each production a set of labels for the “next” production, depending on whether we did the production or not.

So we might write a grammar like:

1: S->aSa {2} {3}

This means that if we do the production S->aSa we next go to production 2. If we don’t, we next go to production 3

2: S->bSb {1,4}{3}

Now, if we do this production, we have a choice of 2 production rules to follow. We can go do 1 again, or we can go to 3.

3: S->a {}{}

If we have a terminal, we have no choice for the next production.

4: S->b {} {}

So, this grammar could produce the string ababa by the productions:

1: S=>aSa. Next, we go to 2.

2: aSa=>abSba. Next, we’ll go to 1 (we could have also gone to 4)

1: abSba=>abSba (we decide not to do the production, and so go to 3)

3: abSba=>ababa. (we stop because we have no non-terminals left)

**Reduction: **The paper by Shamir and Beeri has the reduction, but I have a hard time following their notation, so I will try to rephrase it. The reduction is from 3-CNF-Satisfiability.

What we’ll do is start with a CNF formula. We’ll start by creating a CFG that generates strings where for each clause (l1, l2, l3) we generate all combinations of T1, T2, T3, F1, F2, and F3 with at least one T. This will represent the ways we can make a clause true. The T’s and F’s will be non-terminals.

Now we will try to replace the T’s and F’s with the actual literals from the formula with the following rules:

1: T1-> q1 {2}{3}

2: T1->q1 {2} {4}

3: T1->~q1 {3}{5}

4: F1->~q1 {4}{6}

5: F1->q1 {5}{6}

Rule 6 starts the process again on the next literal. The idea is that with rule 1 we either replace T1 with q1 (setting variable q1 to true, and sending us down a chain that will replace all F1’s with ~q1) or won’t (which will send us to rule 3, where we set T1 to ~q1, meaning we set q1 to false, and go down that chain of replacements).

Our question then becomes can this grammar can generate the original input string of the formula?

**Difficulty: **7. I had an alternate formulation where I replaced each literal with T or F and tried to form a chain of all T’s. I couldn’t think of a way to let the grammar define “at least one T in a clause” and still keep it context-free (a production like TTT->”yes” is not context-free because there is more than one non-terminal on the left side), which I think is why this solution goes the other direction (the final string has the literals, where for mine, the literals in the formula were non-terminals and I wanted my terminal string to be “Yes”). But the idea of using the program to “choose” whether a variable is set to true or false, and then you’re forced to use the substitutions given in the program to keep all of the other replacements of that variable the same isn’t that hard to get.