Unrestricted Grammars

Learn about the formal definition of unrestricted grammar and its application in generating different languages.

What made context-free grammars “context-free” was that the left-hand side of each rule consisted of only a single variable, allowing substitution for that variable wherever it appears in a derivation, i.e., independent of its “context.” An unrestricted grammar (aka “Type 0 grammar”) allows multiple symbols, both terminals (except for λ, which serves no purpose on the rule’s left-hand side) and nonterminals, on the left-hand side of rules, allowing substitution to be sensitive to the context surrounding variables. For example, the rule RaaRRa\to aR allows swapping those two symbols in a derivation, but only applies when the variable RR is followed immediately by the symbol aa.

Definition of unrestricted grammar

An unrestricted grammar is a rewriting system with rules of the form sts\to t, where s,t(ΣV)+s,t\in (\Sigma\cup V)^+ (except tt could also be λ\lambda) and ss contains at least one variable from VV.

The following unrestricted grammar generates {anbncn    n0}\{a^nb^nc^n \;|\; n \geq 0\}:

Get hands-on with 1200+ tech skills courses.