QUASI-DETERMINISTIC OL SYSTEMS AND THEIR REPRESENTATION

A 0L system is called a quasi-deterministic 0L system or a D'0L system for short if there is an integer C such that the cardinality of the s et of words generated in n steps is less than C for every n. D'0L syst ems form a subfamily of the family of 0L systems. It is shown that a 0 L system is effectively decidable whether it is a D'0L system or not a nd the derivations of a D'0L system are represented by the derivations of an HFD0L system. Using these results, the family of languages gene rated by D'0L systems is characterized in the families of HD0L languag es, HFD0L languages, EFD0L languages, ND0L languages, D0L languages, a nd 0L languages. It is also shown that the equivalence problem between context-free languages and the family of D'0L languages and the regul arity and the context-freeness problems for the family of D'0L languag es are decidable.