GATE 2008-IT
April 5, 2025Nielit Scientist-B CS 4-12-2016
April 5, 2025Nielit Scientist-B CS 4-12-2016
|
Question 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 matches the first half
|
|
|
All of the above
|
Question 1 Explanation:
It is the disadvantage or lack of property of a DFA that it cannot remember an arbitrarily such large amount of data which makes it incapable of accepting such languages like palindrome, reversal, etc.
Correct Answer: D
Question 1 Explanation:
It is the disadvantage or lack of property of a DFA that it cannot remember an arbitrarily such large amount of data which makes it incapable of accepting such languages like palindrome, reversal, etc.