World Library  
Flag as Inappropriate
Email this Article

Unrestricted grammar

Article Id: WHEBN0004906174
Reproduction Date:

Title: Unrestricted grammar  
Author: World Heritage Encyclopedia
Language: English
Subject: Context-sensitive grammar, Chomsky hierarchy, Formal grammar, NooJ, Production (computer science)
Collection: Formal Languages
Publisher: World Heritage Encyclopedia

Unrestricted grammar

In formal language theory, an unrestricted grammar is a formal grammar on which no restrictions are made on the left and right sides of the grammar's productions. This is the most general class of grammars in the Chomsky–Schützenberger hierarchy, and can generate arbitrary recursively enumerable languages.


  • Formal definition 1
  • Unrestricted grammars and Turing machines 2
  • Computational properties 3
  • See also 4
  • References 5

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 (actually, this is not strictly necessary since unrestricted grammars make no real distinction between the two; the designation exists purely so that one knows when to stop generating sentential forms of the grammar), 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.[1]:220 As the name implies, there are no real restrictions on the types of production rules that unrestricted grammars can have.

Unrestricted grammars and Turing machines

It may be shown that unrestricted grammars characterize the recursively enumerable languages. This is the same as saying that for every unrestricted grammar G there exists some Turing machine capable of recognizing L(G) and vice versa. Given an unrestricted grammar, such a Turing machine is simple enough to construct, as a two-tape nondeterministic Turing machine. The first tape contains the input word w to be tested, and the second tape is used by the machine to generate sentential forms from G. The Turing machine then does the following:

  1. Start at the left of the second tape and repeatedly choose to move right or select the current position on the tape.
  2. Nondeterministically choose a production \beta \to \gamma from the productions in G.
  3. If \beta appears at some position on the second tape, replace \beta by \gamma at that point, possibly shifting the symbols on the tape left or right depending on the relative lengths of \beta and \gamma (e.g. if \beta is longer than \gamma, shift the tape symbols left).
  4. Compare the resulting sentential form on tape 2 to the word on tape 1. If they match, then the Turing machine accepts the word. If they don't, the Turing machine will go back to step 1.

It is easy to see that this Turing machine will generate all and only the sentential forms of G on its second tape after the last step is executed an arbitrary number of times, thus the language L(G) must be recursively enumerable.

The reverse construction is also possible. Given some Turing machine, it is possible to create an unrestricted grammar.

Computational properties

The decision problem of whether a given string s can be generated by a given unrestricted grammar is equivalent to the problem of whether it can be accepted by the Turing machine equivalent to the grammar. The latter problem is called the Halting problem and is undecidable.

Recursively enumerable languages are closed under Kleene star, concatenation, union, and intersection, but not under set difference; see Recursively enumerable language#Closure properties.

The equivalence of unrestricted grammars to Turing machines implies the existence of a universal unrestricted grammar, a grammar capable of accepting any other unrestricted grammar's language given a description of the language. For this reason, it is theoretically possible to build a programming language based on unrestricted grammars (e.g. Thue).

See also


  1. ^  
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from World eBook Library are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.