CSC 341: March 14, 2007
From CSWiki
Contents |
Instructor's notes for the class session
Semi-Thue processes
To add power to the model of computation that uses context-free grammars, we extend and generalize the notion of a grammar to include single-step derivation rules in which the left-hand side need not be a single variable, but can contain any string of symbols. Instead of designating a variable as a starting point for computation, we consider the more general binary string relation of derivability in the grammar. The distinction between variables and terminals drops away in the new context.
In specifying a semi-Thue process, then, we just identify a non-empty, finite alphabet of symbols and a set of semi-Thue productions -- rules akin to the rules of context-free grammars, but with no contraints on the left-hand side. We retain the idea that a process operates on a "current string" by performing a straightforward substring replacement in which one occurrence of the left-hand side of a production is removed and the right-hand side of the same production is inserted at the same point.
The word problem for a semi-Thue process is the problem of determining, given any strings w and w' on the process's alphabet, whether it is possible to derive w' from w. In some cases, such as Π2 in the handout, there is a relatively straightforward algorithm for solving the word problem; in other cases, even ones that seem simple at first, the solution is surprisingly elusive.
The equivalence of the Turing-machine and semi-Thue-process models
We can model the operation of any Turing machine in a semi-Thue process, essentially by representing configurations of the Turing machine as strings in an alphabet and possible transitions of the Turing machine as productions indicating the effects of those transitions on the configuration strings. By doing a little pre- and post-processing, we can convert the question of whether a given Turing machine M accepts a given string s into an instance of the word problem for the semi-Thue process ΠM that simulates M.
Conversely, given a semi-Thue process Π, we can construct a Turing machine that simulates its operation, and even (with a little pre-processing) convert any instance of the word problem for Π into the question of whether Turing machine MΠ that simulates Π accepts a particular string as input.
The word problem for Thue processes
A Thue process is a semi-Thue process in which, for every production 
of the process, 
is also a production of the process. In other words, all productions are invertable, applicable in either direction. Since this class of processes is much more restrictive, one might imagine that word problems for them would be easier to solve, but this turns out not to be the case. The Post-Markov theorem shows that, in a semi-Thue process that simulates a deterministic Turing machine (with slightly more elaborate constraints on the processes used to implement the simulation), the execution of the process is so constrained that using one of the inverse productions simply backs up one step in the computation -- which is pointless, since from that point there is nothing to do except take the same forward step again (or back up further, to a point at which the same situation holds).
This means that Thue processes can also be used to simulate Turing machines and thus provide another computational model of equivalent power.
Study questions
- Construct the semi-Thue process that simulates the operation of the Turing machine M2, the state diagram for which is shown in Figure 3.8 of our textbook (page 144).
- Show how to derive a string containing qaccept from
in the semi-Thue process constructed in the previous question.
- Describe how to construct an enumerator for the set of strings that could be derived from a given string w in a semi-Thue process Π.
