Is there a programming language that only has the power of a deterministic push-down automata, and no more?

Question

Some programming problems don't require the full power of a Turing machine to solve. They can be solved with much less power. I am seeking a programming language with lesser power.

Does there exist a high-level programming language that is constrained to support just these capabilities:

1. A stack with operations to push values onto the stack and pop values off the stack.

2. A finite state machine (FSM) to input values, move from state to state, interact with the stack, and output results.

I realize that I could use Java or C or Python (etc.) and constrain the language by writing a program that just uses a stack and a FSM. However, I am seeking a programming language that just has these capabilities and no more.

In other words, I don't want to use a Turing-complete programming language to solve problems that only requires the power of a deterministic push-down automata. I want to use a programming language that only has the power of a deterministic push-down automata.

But

Answer 1

In short, you're not going to find a high level language with that little power. This isn't strictly by definition, but high level implies a certain amount of abstraction that corresponds to complexity.

However, this isn't an issue: you don't need to be worried about using too much power. Machine language, the canonically efficient language (minimal overhead!) is Turing complete, indicating that efficiency is not tightly bound to theoretical power.

Giselle

Maybe the asker wasn't looking for efficiency but instead the nice properties that come with using a computational model with less power than a Turing Machine? Maybe he was looking to be able to reason about properties of his program that would be undecidable with a Turing Machine, but that is decidable for a less powerful computational model. – Reiterant

Good point, thank you! I think the answer probably still comes back to "you probably wouldn't call it a programming language if it had that little power." I suspect you might find this sort in sort of "glue" languages or maybe in simple scripting engines, although I can't find a good example. Regular expressions (in their simple form) are canonically equal power to a finite state machine though. This question #315840 has some interesting answers. – Giselle

Answer 2

I'm not sure if this counts, but the LR(1) grammars capture precisely the power of deterministic PDAs - if there's an LR(1) grammar for a language, there's a deterministic PDA for it and vice-versa. Therefore, if you look at tools like yacc or bison, set them to use LR(1) grammars, and disallow semantic actions with arbitrary code in them, you could argue that what you're left with is a programming environment with precisely the power of a deterministic PDA. It's a bit of a stretch, admittedly. :-)

Hope this helps!

Dualism