• Recursively enumerable language
• Unrestricted grammar
  • Formal definition
• Semi-Thue system

Recursively enumerable language

Unrestricted grammar

In automata theory, the class of unrestricted grammars (also called semi-Thue, type-0 or phrase structure grammars) is the most general class of grammars in the Chomsky hierarchy. No restrictions are made on the productions of an unrestricted grammar, other than each of their left-hand sides being non-empty. This grammar class can generate arbitrary recursively enumerable languages.

Formal definition

An unrestricted grammar is a formal grammar $ G=(N,\Sigma ,P,S) $, where $ N $ is a set of nonterminal symbols, $ \Sigma $ is a set of terminal symbols, $ N $ and $ \Sigma $ are disjoint, $ P $ is a set of production rules of the form $ \alpha \to \beta $ where $ \alpha $ and $ \beta $ are strings of symbols in $ N\cup \Sigma $ and $ \alpha $ is not the empty string, and $ S\in N $ is a specially designated start symbol. As the name implies, there are no real restrictions on the types of production rules that unrestricted grammars can have.

Semi-Thue system

In theoretical computer science and mathematical logic a string rewriting system (SRS), historically called a semi-Thue system, is a rewriting system over strings from a (usually finite) alphabet. Given a binary relation $ R $ between fixed strings over the alphabet, called rewrite rules, denoted by $ s\rightarrow t $, an SRS extends the rewriting relation to all strings in which the left- and right-hand side of the rules appear as substrings, that is $ usv\rightarrow utv $, where $ s $, $ t $, $ u $, and $ v $ are strings.