Esiste un linguaggio di programmazione che ha solo il potere di un automa push-down deterministico, e non di più?

Question

Alcuni problemi di programmazione non richiedono la piena potenza di una macchina di Turing da risolvere. Possono essere risolti con molta meno energia. Sto cercando un linguaggio di programmazione con minore potenza.

Does esiste un linguaggio di programmazione di alto livello che è costretto a sostenere solo queste funzionalità:

1. Una pila con le operazioni per spingere i valori sui valori dello stack e pop dallo stack.

2. Una macchina a stati finiti (FSM) per immettere valori, passare da stato a stato, interagire con lo stack e generare risultati.

mi rendo conto che avrei potuto usare Java o C o Python (etc.) e vincolare la lingua, scrivendo un programma che utilizza solo una pila e un FSM. Tuttavia, sto cercando un linguaggio di programmazione che abbia solo queste capacità e non di più.

In altre parole, non voglio usare un linguaggio di programmazione completo di Turing per risolvere problemi che richiedono solo la potenza di un automa push-down deterministico. Voglio usare un linguaggio di programmazione che abbia solo il potere di un automa push-down deterministico.

Answer 1

In breve, non troverai un linguaggio di alto livello con quel piccolo potere. Questo non è strettamente per definizione, ma il livello alto implica una certa quantità di astrazione che corrisponde alla complessità.

Tuttavia, questo non è un problema: non è necessario preoccuparsi di usare troppa energia. Il linguaggio macchina, il linguaggio canonicamente efficiente (overhead minimo!) È completo di Turing, indicando che l'efficienza non è strettamente legata al potere teorico.

Answer 2

Non sono sicuro che ciò conti, ma le grammatiche LR (1) acquisiscono esattamente il potere dei PDA deterministici - se c'è una grammatica LR (1) per una lingua, c'è un PDA deterministico per questo e viceversa . Quindi, se guardi strumenti come yacc o bison, li imposti per usare le grammatiche LR (1) e non permetti azioni semantiche con codice arbitrario in essi, potresti obiettare che quello che ti rimane è un ambiente di programmazione con esattamente il potere di un PDA deterministico. È un po 'difficile, devo ammetterlo. :-)

Spero che questo aiuti!