Definition
A Post canonical system is a triplet (A,I,R), where
- A is a finite alphabet, and finite (possibly empty) strings on A are called words.
- I is a finite set of initial words.
- R is a finite set of string-transforming rules (called production rules), each rule being of the following form:
where each g and h is a specified fixed word, and each $ and $' is a variable standing for an arbitrary word. The strings before and after the arrow in a production rule are called the rule's antecedents and consequent, respectively. It is required that each $' in the consequent be one of the $s in the antecedents of that rule, and that each antecedent and consequent contain at least one variable.
In many contexts, each production rule has only one antecedent, thus taking the simpler form
The formal language generated by a Post canonical system is the set whose elements are the initial words together with all words obtainable from them by repeated application of the production rules. Such sets are precisely the recursively enumerable languages.
Read more about this topic: Post Canonical System
Famous quotes containing the word definition:
“... if, as women, we accept a philosophy of history that asserts that women are by definition assimilated into the male universal, that we can understand our past through a male lensif we are unaware that women even have a historywe live our lives similarly unanchored, drifting in response to a veering wind of myth and bias.”
—Adrienne Rich (b. 1929)
“Scientific method is the way to truth, but it affords, even in
principle, no unique definition of truth. Any so-called pragmatic
definition of truth is doomed to failure equally.”
—Willard Van Orman Quine (b. 1908)
“No man, not even a doctor, ever gives any other definition of what a nurse should be than thisdevoted and obedient. This definition would do just as well for a porter. It might even do for a horse. It would not do for a policeman.”
—Florence Nightingale (18201910)