[Solved]: Are there undecidable properties of non-turing-complete automata?

Problem Detail: 

Are there undecidable properties of linear bounded automata (avoiding the empty set language trick)? What about for a deterministic finite automaton? (put aside intractability).

I would like to get an example (if possible) of an undecidable problem that is defined without using Turing machines explicitly.

Is Turing completeness of a model necessary to support uncomputable problems?

Asked By : Hernan_eche

Answered By : David Lewis

Undecidable problems about context free grammars, and hence, pushdown acceptors as well, which are restricted TMs from Wikipedia...

1. Given a CFG, does it generate the language of all strings over the alphabet of terminal symbols used in its rules?

2. Given two CFGs, do they generate the same language?

3. Given two CFGs, can the first generate all strings that the second can generate?

There are many others about CFGs/PDAs as well as CSGs/LBAs and many other "simpler than TM" models.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1697