NIELIT 2016 DEC Scientist B (CS) - Section B: 1

Question

Palindromes can't be recognized by any Finite State Automata because:

• A. FSA cannot remember arbitrarily large amount of information.
• B. FSA cannot deterministically fix the midpoint.
• C. Even if the mid-Point is known an FSA cannot find whether the second half of the string matches the first half.
• D. All of the above.

Comments

D option is correct

Answer 1

FSA has finite memory

FSA is not able to find midpoint in palindrome.

FSA has finite memory so, even if midpoint is known an FSA cannot find whether the second half of the string matches the first half.

D) All of the above

Comments

FSA has memory -- just that it is finite.

---

ok, FSA has memory but only finite memory

---

Sir,even though FA has finite memory,still it can remember infinite information by making use of loop. Am I right ??

Option A is not right framing for this question

---

Here for FSM finite means that the DFA has finite number of states which is treated as a memory element which is finite ... And those finite number states can be used to recognise infinite length strings... Also every finite language  but every infinite language can be regular or non regular

Answer 2

You need to understand that FSA means finite state automata and hence they have a very little memory to keep track of last input . 

Palindrome problem requires two basic constraint 

1. Find the midpoint 
2.  Match with the subsequent previous inputs . 

Now FSA cannot do either of them and hence option D is most suitable .

 

Answer 3

option D All of the above are correct.

FA have  finite memory.
FA is not capable of finding mid point in palindrome.
FA is not capable of comparing strings.