Extra: Unrestricted Grammars

We defined regular grammars by adding additional restrictions to the definition of a context-free grammar. If we instead loosen restrictions, we get what is called an Unrestricted Grammar

Unrestricted grammars aren’t used much in practice because they are hard to work with (and no parsing algorithm exists). However, it is interesting to know that they exist.

Definition

An Unrestricted Grammar is specified by a 4-tuple $(\Sigma, {\cal V}, S, {\cal R})$ , where

$\Sigma$ is an alphabet; the members of $\Sigma$ are called terminals.
${\cal V}$ is a (disjoint!) alphabet; the members of $\cal V$ are called nonterminals.
$S\in {\cal V}$ is called the start symbol
$\cal R$ is a set of rules of the form $L\to R$ where $L,R\in(\Sigma\cup {\cal V})^{*}$ .

In other words, an unrestricted grammar is just like a context-free grammar except the left-hand-side doesn’t have to be a single nonterminal.

Example

The following grammar produces the (non-context-free!) language $\{\ \mathtt{a}^n\mathtt{b}^n\mathtt{c}^n\ \ |\ n\geq 1\ \}$ :

\begin{array}{lcl} S & \to & \mathtt{abc}\\ S & \to & \mathtt{a}SQ\\ \mathtt{b}Q\mathtt{c} & \to & \mathtt{bbcc}\\ \mathtt{c}Q & \to & Q\mathtt{c}\\ \end{array}

For example,

S \Rightarrow \mathtt{a}SQ \Rightarrow \mathtt{aabc}Q \Rightarrow \mathtt{aab}Q\mathtt{c} \Rightarrow \mathtt{aabbcc}.

where we replaced $\mathtt{c}Q$ by $Q\mathtt{c}$ in the third step and replaced $\mathtt{b}Q\mathtt{c}$ by $\mathtt{bbcc}$ in the fourth step.

We can read the rule

\mathtt{b}Q\mathtt{c} \to \mathtt{bbcc}

as saying “we can replace $Q$ by bc, but only if that $Q$ appears in-between b and c.” In other words, whether we can replace $Q$ by bc depends on the context in which $Q$ appears; the rule is context-sensitive.

In contrast, the rule

Q \to \mathtt{bc}

lets us replace $Q$ by bc no matter where $Q$ appears, i.e., no matter what context $Q$ appears in. Such rules are therefore called context-free, and this is where the terminology of CFLs and CFGs comes from.

Example

Any language we can imagine computing can be described by some unrestricted grammar. For example, the following grammar produces all sequences of a’s whose length is composite (i.e., whose length is not a prime number):

\begin{array}{lcl} S & \to & H\mathtt{a}C \\ C & \to & \mathtt{a}C \\ C & \to & \mathtt{a}T \\ T & \to & ZU \\ AZ & \to & ZA \\ \mathtt{a}Z & \to & ZA\mathtt{a} \\ HZ & \to & HY\\ YA & \to & AY \\ Y\mathtt{a} & \to & \mathtt{a}Y \\ YU & \to & T \\ T & \to & X \\ \mathtt{a}X & \to & X\mathtt{a}\mathtt{a} \\ AX & \to & X\mathtt{a} \\ HX & \to & \epsilon\\ \end{array}