Pushdown Automata Free of Explicit Nondeterminism and an Infinite Hierarchy of Context-free Languages

• Autorzy: Bedregal B.R.C.
• Języki publikacji: EN

Abstrakty

EN

By explicit nondeterminism degree of a pushdown automata we mean the maximal number of choices in the transitions of the automata. In this paper we will prove that each pushdown automaton has an equivalent pushdown automaton with degree 1 of explicit nondeterminism, which implies that l-moves in pda are sufficient to simulate nondeterminism. Moreover, from this normal form (i.e. pda with degree 1 of explicit nondeterminism) we can measure the amount of (implicit) nondeterminism. This measure will be used to determine a countable infinite hierarchy of context-free language subclasses, whose bottom is the class of deterministic context-free languages and the top is the class of context-free languages.

Słowa kluczowe

EN

pushdown automata; amount of nondeterminism; lambda-moves; hierarchy; implicit amd explicit nondeterminism

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 81, nr 4
• Strony: 367--377
• Opis fizyczny: bibliogr. 8 poz., wykr.

Twórcy

autor

Bedregal B.R.C.

• Campus Universitaruio s/n, Lagoa, Nova, Natal_RN, Brazil, CEP-59.072-970,

Bibliografia

• [1] Goldstine, J., Leung, H., Wotschke, D.: Measuring nondeterminism in pushdown automata, Journal of Computer and System Sciences 71(4), 2005, 440-466.
• [2] Harrison, M.A.: Introduction to Formal Language Theory, Addison-Wesley, Reading, MA, 1978.
• [3] Herzog, C.: Pushdown automata with bounded nondeterminism and bounded ambiguity, Theoretical Computer Science 181(1-2), 1997, 141-157.
• [4] Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading, MA, 1979.
• [5] Li, M., Vitanyi, P.M.B.: A new approach to formal language theory by Kolmogorov complexity, SIAM J. Comput., 24(2), 1995, 398-410.
• [6] Salomaa, K., Yu, S.: Measures of nondeterminism for pushdown automata, Journal of Computer and System Sciences 49(2), 1994, 362-374.
• [7] Vermeir, D., Savitch, W.J.: On the amount of nondeterminism in pushdown automata, Fundamenta Informaticae 4, 1981, 401-418.
• [8] Yu, S.: A pumping lemma for deterministic context-free languages. Information Processing Letters, 31, 1989, 47-51.