Ambiguity in Finite Automata

Forfattere

  • Erik Meineche Schmidt

DOI:

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

Resumé

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.

Forfatterbiografi

Erik Meineche Schmidt

Downloads

Publiceret

1977-09-01

Citation/Eksport

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

Nummer

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

Sektion

Articles

Licens

Creative Commons License

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