COMPUTER SCIENCE AND ENGINEERING
THEORY OF COMPUTATION
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
accepted by DFA
|
|
|
accepted by PDA
|
|
|
accepted by LBA
|
|
|
accepted by Turing machine
|
Detailed explanation-1: -A language is accepted by a deterministic finite automaton if and only if it is accepted by a regular expression. (single letter) a ∈ RegEx L(a) = a (variable) L ∈ RegEx where L is a language variable. (union) E + F ∈ RegEx L(E + F) = L(E) ∪ L(F) (concatenation) E.F ∈ RegEx L(E.F) = L(E).
Detailed explanation-2: -A regular language satisfies the following equivalent properties: it is the language of a regular expression (by the above definition) it is the language accepted by a nondeterministic finite automaton (NFA) it is the language accepted by a deterministic finite automaton (DFA)
Detailed explanation-3: -A language is regular if and only if some nondeterministic finite automaton recognizes it. The class of regular languages is closed under the union operation.
Detailed explanation-4: -Explanation: A language is regular if and only if it can be accepted by a finite automaton.
Detailed explanation-5: -That is, the language accepted by a DFA is the set of strings accepted by the DFA. Example 1 : This DFA accepts because it can go from the initial state to the accepting state (also the initial state) without reading any symbol of the alphabet i.e. by reading an empty string .