I'm conscious that Bitcoin's script is not turing complete, as multiple answers point out (e.g., this answer and this one). 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.
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 xs) 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.
