Characterizations of stack uniform strict deterministic languages.
Jan Pittl · Czech digital mathematics library · 1981
Three new characterizations for the class of languages accepted with empty store by a stack uniform deterministic pushdown automaton are presented.This class is shown to coincide with the classes of languages generated by length uniform grammars and length uniform strict deterministic grammars respectively.The result is then used for proving the interesting fact that the power of nondeterministic stack uniform automata is the same, i.e. all the four devices mentioned above possess the same capability of defining languages.