1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for taking the time to reply but these are mostly known to me, and not what I intended to communicate. For example when I talked about the lambda calculus in contrast to Turing machines I was referring to fact that they are of equal computational power but writing programs in the lambda calculus tends to be easier. Writing out finite state machines is kind of like working with Turing machines. I was asking if there is a Lambda calculus type system for finite automate. $\endgroup$ – 44701 Feb 6 '16 at 22:11
  • $\begingroup$ In relation to the grammars question. I understood the first bit but you answered my actual question in the next bit: "Regular grammars indeed generate all (and only) regular languages, and it's not too hard to show this by interpreting them as NFAs (exercise)." $\endgroup$ – 44701 Feb 6 '16 at 22:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.