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}
>\]
Previous: 6.15 Regular Grammars
Next: 6.17 Turing Machines