Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Calculi for a computability class

, ,
Problem Detail:

Proving two push down automata equivalent is undecidable. But proving two finite state machines equivalent is decidable. You also cannot write a programming language that allows expressing the complete set of push down automata, with nothing more powerful.

First question: Can a language exist that expresses up to the power of finite state machines but nothing higher?

Next. Working at the power of Turing machines we have the lambda calculus which with a little bit of sugar is a nice programming language. In addition there are weaker forms of the lambda calculus that are not Turing complete such as the simply typed lambda calculus.

Second question: What calculi exist that cannot express problems above finite state machines, but a programming language could be built on top of. Kind of like the lambda calculus.

Grammars can be restricted to only allow regular languages. This of course does not change the fact that context free grammars can represent regular languages.

Third question: Even though context free grammars allow the expression regular languages, do the methods used to check if a grammar is regular allow the expression of all regular languages? Such as those talked about in "https://en.wikipedia.org/wiki/Regular_grammar".

These questions are all directly related. Pardon how convoluted this is.

#### Answered By : Yuval Filmus

You are asking several questions. Let me answer them one by one, though not in the same order.

Even though context free grammars allow the expression regular languages, do the methods used to check if a grammar is regular allow the expression of all regular languages? You are misunderstanding the article. One does not check that a grammar is regular. Rather, we define a grammar as regular if it satisfies the constraints described in the article. Regular grammars indeed generate all (and only) regular languages, and it's not too hard to show this by interpreting them as NFAs (exercise).

As an aside, the following is undecidable: given a context-free grammar, check whether the language it generates is regular.

Can a language exist that expresses up to the power of finite state machines but nothing higher? Yes, for example the language of regular expression, the language of DFAs, the language of NFAs, the language of regular grammars, and so on.

What calculi exist that cannot express problems above finite state machines, but a programming language could be built on top of. Kind of like the lambda calculus. This question is not really well defined, and it is very easy to cheat. A reasonably natural example is finite automata – if you add two stacks you get a model having the same power as a full-fledged Turing machine.

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

3.2K people like this