<p>No, it's much less expressive than a PDA, or even a DFA.  There's a stack, but what you don't have is the ability to return to the same program state with different stack contents, or for that matter, to return to the same program state at all.  </p>

<p>Execution is linear and there are no loops, so any given instruction in the script is executed at most once.  And each instruction can only inspect a bounded number of stack or input elements.  So a Bitcoin script cannot even recognize the language <code>x*</code> (any number of <code>x</code>s) because a script of length <em>n</em> will only ever be able to look at, say, 4n elements of input, and it cannot distinguish <code>xxxx....xx</code> from <code>xxxx....xy</code> if both strings have length greater than, say, 4n+1.  Even a DFA can recognize that language.</p>

CC BY-SA 4.0
2018-07-22T20:10:31.450Z
Now I know that there is a language that script cannot accept and DFA accepts. I am wondering if there is an example that works for script and not for DFA.
Briomkez
CC BY-SA 4.0
2018-07-23T06:06:22.407Z
@Briomkez: There can't be; you can encode any script as a DFA in a very straightforward fashion.
Nate Eldredge
CC BY-SA 4.0
2018-07-16T21:05:35.907Z
2018-07-16T21:05:35.907Z
Nate Eldredge
<p>I'm conscious that Bitcoin's script is not turing complete, as multiple answers point out (e.g., <a href="https://bitcoin.stackexchange.com/questions/17258/turing-completeness-of-bitcoin-script">this answer</a> and <a href="https://bitcoin.stackexchange.com/questions/25427/the-bitcoin-scripting-system-is-purposefully-not-turing-complete-why">this one</a>). But I'm wondering if script can express the language of a PDA or equivalently, of a context-free-grammar.</p>

<p>I think it should be so, because of script's stack, but I'm not sure and therefore I ask for some clarifications/confirmations.</p>

<script>
Bitcoin's script expressivity
Briomkez
# Bitcoin's script expressivity

(Asked by: username_0 on 2018-07-16)

I'm conscious that Bitcoin's script is not turing complete, as multiple answers point out (e.g., [this answer](https://bitcoin.stackexchange.com/questions/17258/turing-completeness-of-bitcoin-script) and [this one](https://bitcoin.stackexchange.com/questions/25427/the-bitcoin-scripting-system-is-purposefully-not-turing-complete-why)). But I'm wondering if script can express the language of a PDA or equivalently, of a context-free-grammar.

I think it should be so, because of script's stack, but I'm not sure and therefore I ask for some clarifications/confirmations.

**Tags:** script


---

## 1 answers

### Answer by username_1 on 2018-07-16. Score: 3 | Accepted answer

No, it's much less expressive than a PDA, or even a DFA. There's a stack, but what you don't have is the ability to return to the same program state with different stack contents, or for that matter, to return to the same program state at all.

Execution is linear and there are no loops, so any given instruction in the script is executed at most once. And each instruction can only inspect a bounded number of stack or input elements. So a Bitcoin script cannot even recognize the language `x*` (any number of `x`s) because a script of length *n* will only ever be able to look at, say, 4n elements of input, and it cannot distinguish `xxxx....xx` from `xxxx....xy` if both strings have length greater than, say, 4n+1. Even a DFA can recognize that language.

> **Comments:**
> **username_0**: Now I know that there is a language that script cannot accept and DFA accepts. I am wondering if there is an example that works for script and not for DFA.  
> **username_1**: @username_0: There can't be; you can encode any script as a DFA in a very straightforward fashion.  

---

