Accept (automata and complexity theory)
Acceptance is a term from automaton and complexity theory , sub-areas of theoretical computer science . The property that an automaton accepts input is closely related to decidability .
- An algorithm accepts a language A if and only if it returns a positive answer for exactly the elements from A.
- An algorithm decides a language A if and only if it terminates in each case and returns a positive answer for exactly the elements from A (this implies that it returns a negative answer for all inputs that are not in A).
The distinction between accepting and deciding is particularly important if the calculation is nondeterministic (see also NP (complexity class) ) or if there can be infinitely long calculations (see recursive enumeration ).
literature
- Uwe Schöning : Theoretical Computer Science - in a nutshell . Spectrum Academic Publishing House , 2001, ISBN 3-8274-1099-1 .
Web links
Wiktionary: accept - explanations of meanings, word origins, synonyms, translations