String Rewriting Systems, Type-0 Formal Grammars
A string rewriting system is a special type of Post canonical system with a single initial word, and the productions are each of the form
That is, each production rule is a simple substitution rule, often written in the form g → h. It has been proved that any Post canonical system is reducible to such a substitution system, which, as a formal grammar, is also called a phrase-structure grammar, or a type-0 grammar in the Chomsky hierarchy.
Read more about this topic: Post Canonical System
Famous quotes containing the words string, formal and/or grammars:
“A culture may be conceived as a network of beliefs and purposes in which any string in the net pulls and is pulled by the others, thus perpetually changing the configuration of the whole. If the cultural element called morals takes on a new shape, we must ask what other strings have pulled it out of line. It cannot be one solitary string, nor even the strings nearby, for the network is three-dimensional at least.”
—Jacques Barzun (b. 1907)
“Two clergymen disputing whether ordination would be valid without the imposition of both hands, the more formal one said, “Do you think the Holy Dove could fly down with only one wing?””
—Horace Walpole (1717–1797)
“The violent illiteracies of the graffiti, the clenched silence of the adolescent, the nonsense cries from the stage-happening, are resolutely strategic. The insurgent and the freak-out have broken off discourse with a cultural system which they despise as a cruel, antiquated fraud. They will not bandy words with it. Accept, even momentarily, the conventions of literate linguistic exchange, and you are caught in the net of the old values, of the grammars that can condescend or enslave.”
—George Steiner (b. 1929)