Open AccessAmbiguity in Finite Automata
Author(s) -
Evanthia Kalpazidou Schmidt
Publication year - 1977
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v6i82.6498
Subject(s) - succinctness , deterministic finite automaton , nondeterministic finite automaton , alphabet , finite state machine , regular expression , discrete mathematics , quantum finite automata , nondeterministic algorithm , automaton , mathematics , combinatorics , bounded function , dfa minimization , ambiguity , ω automaton , nested word , regular language , computer science , automata theory , theoretical computer science , algorithm , programming language , linguistics , mathematical analysis , philosophy
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.