Ambiguity in Finite Automata

Authors

  • Erik Meineche Schmidt

DOI:

https://doi.org/10.7146/dpb.v6i82.6498

Abstract

The gain in succinctness of descriptions of regular languages when nondeterministic (unambiguous) finite automata are used rather than unambiguous (deterministic) finite automata, is not bounded by any polynomium.

The problem of deciding whether an unambiguous regular expression does not generate all words over its terminal alphabet, is in NP.

Author Biography

Erik Meineche Schmidt

Downloads

Published

1977-09-01

How to Cite

Schmidt, E. M. (1977). Ambiguity in Finite Automata. DAIMI Report Series, 6(82). https://doi.org/10.7146/dpb.v6i82.6498

Issue

No. 82 (1978): PB-82 Ambiguity in Finite Automata

Section

Articles

License

Creative Commons License

Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.