No restrictions are made on the productions of an unrestricted grammar, other than each of their left-hand sides being non-empty.
[1]: 220 This grammar class can generate arbitrary recursively enumerable languages.
, where As the name implies, there are no real restrictions on the types of production rules that unrestricted grammars can have.
[note 2] The unrestricted grammars characterize the recursively enumerable languages.
on its second tape after the last step is executed an arbitrary number of times, thus the language
Given some Turing machine, it is possible to create an equivalent unrestricted grammar[1]: 222 which even uses only productions with one or more non-terminal symbols on their left-hand sides.
Some authors[citation needed] use the latter form as definition of unrestricted grammar.
Recursively enumerable languages are closed under Kleene star, concatenation, union, and intersection, but not under set difference; see Recursively enumerable language#Closure properties.
For this reason, it is theoretically possible to build a programming language based on unrestricted grammars (e.g. Thue).