TAOCP 7.1.1 Exercise 46

Let the terminal alphabet of grammar (43) be $\Sigma=\{a_1,\dots,a_{11}\}$.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.1: Boolean Basics

Exercise 46. [20] Which of the $11 \times 11$ character pairs $xy$ can occur next to each other in the context-free grammar $(43)$?

Verified: yes
Solve time: 2m51s

Let the terminal alphabet of grammar (43) be $\Sigma={a_1,\dots,a_{11}}$. We analyze the structure of the grammar directly.

The productions of grammar (43) include:

  1. $S \to SS$
  2. $S \to a_i$ for each $a_i \in \Sigma$

From these rules, every derivation builds strings by repeatedly concatenating already generated strings and eventually replacing variables by single terminals.

Step 1: Language generated by the grammar

We show that every nonempty string over $\Sigma$ is generated.

  • Each $a_i$ is in the language by $S \to a_i$.
  • If $u, v \in \Sigma^+$, then $uv$ is generated by applying $S \to SS$ and deriving $u$ from the first $S$ and $v$ from the second $S$.

Thus the language is exactly

$$ L = \Sigma^+, $$

the set of all nonempty strings over the 11-symbol alphabet.

Step 2: Characterization of admissible adjacent pairs

A pair $xy$ of terminals is admissible if it occurs as two consecutive symbols in some string in $L$.

Since $L = \Sigma^+$, consider any ordered pair $(a_i,a_j)$.

The string $a_i a_j \in \Sigma^+$, hence $a_i a_j \in L$.

Therefore every ordered pair of terminals occurs as adjacent symbols in some derived string.

Step 3: Conclusion

All $11 \times 11$ terminal pairs are admissible.

That is, the complete set of admissible adjacent pairs is

$$ {(a_i,a_j) \mid 1 \le i \le 11,; 1 \le j \le 11}. $$

$$ \boxed{\text{Every terminal pair } xy \text{ with } x,y \in \Sigma \text{ can occur.}} $$