COMPUTER SCIENCE AND ENGINEERING
THEORY OF COMPUTATION
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
Finite automata cannot deterministically find the midpoint
|
|
|
Finite automata cannot remember arbitarily large amount of data
|
|
|
Even if the mid point is known, it cannot find whether the second half matches the first
|
|
|
All of the mentioned
|
Detailed explanation-1: -Palindromes can’t be recognized by any Finite State Automata because: FSA cannot remember arbitrarily large amount of information. FSA cannot deterministically fix the midpoint. Even if the mid-Point is known an FSA cannot find whether the second half of the string matches the first half.
Detailed explanation-2: -What are the basic limitations of finite state machine? Explanation: Because it does to store its previous state of the transition. Explanation: Palindromes cannot be recognized by FSM.
Detailed explanation-3: -One limitation of finite state machines is that they can only recognize regular languages. Regular languages make up only a small, finite portion of possible languages. See context free grammars and Turing machines.
Detailed explanation-4: -Limitations of Finite Automata The defining characteristic of FA is that they have only a finite number of states. Hence, a finite automata can only “count” (that is, maintain a counter, where different states correspond to different values of the counter) a finite number of input scenarios.
Detailed explanation-5: -Which of the following set can be recognized by a Deterministic Finite state Automaton? The set of binary string in which the number of zeros is the same as the number of ones.