Some descriptional complexity problems in finite automata theory. - Adorna, Henry
Automata Theory is one of the oldest and well studied areas in theoretical computer science. Almost all not very hard problems, yet of main interest have been solved. The excit-ing developments in theoretical computer science for more than two decades ago produced very specialized computer scientists with few knowledge about other areas and much less about the context of fundamental theory. In this paper, We discuss three problems pertaining to descriptional complexity of finite automata. The long standing problem of estimating the size of the minimal nondeterministic finite automaton ns(L) for a regular language L is considered. We present the best so far lower bound for ns(L) for some regular languages L. Some issues related to ambiguity on nondeterministic finite automaton are also discussed. Finally, we discussed the fundamental problem since 1978 about the relationship between 2-Way deterministic finite automaton and 2-way nondeterministic finite automaton. We argue that automata theory has enough basic questions to be resolved. If one wants to put automata theory in the place where it Was once in computer science research, one must not only look at applications of the theory but consider also solving problems of great impact.
Keywords: Descriptional Complexity; Finite Automata; Regular Languages; Lower Bounds