Before revision:  We show that the problem is in O(log log |w|) for languages in an algebraically-defined  class QSG, and that it is in O(1) for another  class QLZG.
After revision:  We show that the problem is in O(log log |w|) for languages in an algebraically-defined , decidable class QSG, and that it is in O(1) for another class QLZG.