Connections With Other Notions
A semi-Thue system is also a term-rewriting system—one that has monadic words (functions) ending in the same variable as left- and right-hand side terms, e.g. a term rule is equivalent with the string rule .
A semi-Thue system is also a special type of Post canonical system, but every Post canonical system can also be reduced to an SRS. Both formalism are Turing complete, and thus equivalent to Noam Chomsky's unrestricted grammars, which are sometimes called semi-Thue grammars. A formal grammar only differs from a semi-Thue system by the separation of the alphabet in terminals and non-terminals, and the fixation of a starting symbol amongst non-terminals. A minority of authors actually define a semi-Thue system as a triple, where is called the set of axioms. Under this "generative" definition of semi-Thue system, an unrestricted grammar is just a semi-Thue system with a single axiom in which one partitions the alphabet in terminals and non-terminals, and makes the axiom a nonterminal. The simple artifice of partitioning the alphabet in terminals and non-terminals is a powerful one; it allows the definition of the Chomsky hierarchy based on the what combination of terminals and non-terminals rules contain. This was a crucial development in the theory of formal languages.
Read more about this topic: Semi-Thue System
Famous quotes containing the words connections with, connections and/or notions:
“Growing up human is uniquely a matter of social relations rather than biology. What we learn from connections within the family takes the place of instincts that program the behavior of animals; which raises the question, how good are these connections?”
—Elizabeth Janeway (b. 1913)
“The quickness with which all the “stuff” from childhood can reduce adult siblings to kids again underscores the strong and complex connections between brothers and sisters.... It doesn’t seem to matter how much time has elapsed or how far we’ve traveled. Our brothers and sisters bring us face to face with our former selves and remind us how intricately bound up we are in each other’s lives.”
—Jane Mersky Leder (20th century)
“Your notions of friendship are new to me; I believe every man is born with his quantum, and he cannot give to one without robbing another. I very well know to whom I would give the first place in my friendship, but they are not in the way, I am condemned to another scene, and therefore I distribute it in pennyworths to those about me, and who displease me least, and should do the same to my fellow prisoners if I were condemned to a jail.”
—Jonathan Swift (1667–1745)