Chomsky hierarchy describes a containment hierarchy of classes of formal grammars. Lower level of languages, like regular and context-free, are well studied, and used in multiple practical fields, like regular expressions, and programming languages parsing.

Most textbooks introduce how to construct deterministic finite automaton from regular expressions, and some textbooks focusing on compilers will present LL, LR, LALR, etc. to show how a subset of context-free grammars are transferred to parsers. These topic are well researched, and if you use bison, it will even show you how reduce-reduce, shift-reduce conflicts are happening by examples.

When the problem comes to higher classes in the Chomsky hierarchy, the problem becomes difficult. C++ has a context-sensitive grammar, and GCC have to use a hand-written parser for it. Most textbooks will stop at context-free grammar, and teach you to use the pumping theorem to prove that some languages are not context-free.

For these languages, it’s even difficult to describe them with a correct grammar! Take $a^n b^n c^n, n \ge 0$ as an example (A popular and easy non-context-free language, commonly used to demonstrate pumping lemma). There are no definitive algorithm to guarantee a grammar for it.

Sentinel and Combination

A common solution for this can be sentinel and combination. In our example, we can first combine the last two part as $a^n (BC)^n$, which can be generated as context-free grammar, and with the sentinel $CB \rightarrow BC$, arrays like $BCBCBC\cdots$ can be derived as $BBB\cdots CCC$.

This can be obscure, if the part increases. We need to either combine recursively, or create larger sentinels to do the part. When the part is not definitive, the problem cannot be solved.

Take this problem as another example:

Let $\Sigma = \{1\}$ and $L_{\text{square}} := \{1^n \mid n \text{ is a perfect square}\}$. So $\epsilon, 1, 1111, 111111111$ are in $L$ but $11, 11111$ are not. Give an unrestricted grammar generating $L_{\text{square}}$.

Square numbers can be expanded to $1 + 2 + \cdots + (n-1) + n + (n-1) + \cdots + 2 + 1$. If we take this route, the problem could be difficult to solve by the combine method, as the items in the sequence increases with $n$.

Now we show a new perspective to view the problem. Taking the string as a queue, and messengers moving along them between head and tail. When certain situations are met, messengers will change the sequence, otherwise they’ll move through the queue.

This method will have longer reductions, but it will be easier and more intuitive to construct, and having less rules.

In the second problem, we separate the 1’s with 0, to specify a border for messengers to recognize. And we add symbols [ and ] to indicate the head and tail. A state in the reduction could be [01011010].

We can have 2 messengers to solve the problem.

• messenger A, from head to tail:
  • insert new groups, i.e. 010, at the head and tail.
  • increase inner groups’ 1 number
• messenger B, from head to tail:
  • remove all zeros, head and tail symbol, to reformat the string into the final look.

With the border of each group, the recognition field, i.e. the range it looks to derive uniquely, decides the size of its rule set. We here define these messengers with grammar:

$$\begin{align*} [ &\rightarrow [01A \\ A0 &\rightarrow 01A \\ A1 &\rightarrow 1A \\ A] &\rightarrow 0] \\ \end{align*}$$

and $B$:

$$\begin{align*} [ &\rightarrow B \\ B0 &\rightarrow B \\ B1 &\rightarrow 1B \\ B] &\rightarrow \epsilon \\ \end{align*}$$

and the start symbol: $S \rightarrow []$. Only 5 variables and 9 rules is needed.

Exercise

1. Give the unlimited grammar generating language in the first problem.

   Hint: You may need to deal with situations when two messengers meet, causing a deadlock. (e.g. Emulate a lock by changing the head symbol to allow at most one messenger traveling in the sequence).

2. Let $\Sigma = \{1\}$ and language $L := \{1^k \mid k \text{ is prime}\}$. Give an unlimited grammar generating $L$.

   Hint: Here is a not-so-clever path doing it:

   • list all numbers by increasing order
   • use Eratosthenes Sieve to filter primes
   • select one and remove others

   Not only head symbols can send messengers, and the direction are not limited from head to tail.

   You may change the head and tail symbol to indicate stages.

   You may need to deal with situations when messengers in different directions meet, causing a deadlock. (e.g. by explicitly swap them with $AB \rightarrow BA$).