View Full Version : How to prove FSA cannot recognise sentences of Lambda calculus ?

March 22nd, 2009, 04:55 PM
Ok, I am a terrible mathematician yet I need to find the proof of this as it will be asked in the midterm of next week.

I think it should start from the defitions of the two constructs concerned and step by step, how can I prove that it is not possible to construct a Finite State Automation to recognise lambda-calculus sentences?