Three one-way heads cannot do string matching

摘要

We prove that three-head one-way DFA cannot perform string matching, that is, no three-head one-way DFA accepts the language L = {x # y|x is a substring of y, where x, y ε {0, 1}*}. This answers the k = 3 case of the question whether a k-head one-way DFA can perform string matching, raised by Galil and Seiferas