Pushdown automata - definition and definition of $\vdash$

Question

I am reading about pushdown automata and I don't understand the definition of $\vdash$.

My book writes that $$(q,aw,Z\alpha)\vdash(p,w,\beta\alpha)$$ if $$(p,\beta)\in\delta(q,a,Z)$$

Can someone please explain to me this definition ?

I understand that the automata is at first in state $q$ and the reminder of the input is $aw$ (so it starts with $a$ so it fits to the second argument of $\delta)$,

but I have problems understanding whats happening with $Z\alpha$ and $\beta\alpha$, is the content of the stack $Z\alpha$ or is it just whats written at the top ? why go from $Z\alpha$ to $\beta\alpha$ ? and actually where is $\alpha$, is it in $\Gamma^{*}$?

another small issue I have: does $\Sigma\subset\Gamma$ ? it is not written in my book but I suspect so.

if it does, does $\Gamma=\Sigma\cup\{\dashv\}$? does $\dashv\not\in\Sigma$ by definition ?

I'm sorry for all this definition questions, it is not defined in my book.

Answer 1

$\Gamma$ is the stack alphabet; it may be entirely disjoint from $\Sigma$, which is the input alphabet.

$(p,\beta)\in\delta(q,a,Z)$ means that if the automaton is in state $q$ with input $a$ and $Z$ on the top of the stack, it goes to state $p$ and replaces $Z$ with $\beta$, where $\beta\in\Gamma^*$ is a finite string of stack symbols. In other words, it pops the single symbol $Z$ and pushes the string $\beta$ onto the stack.

In the statement $(q,aw,Z\alpha)\vdash(p,w,\beta\alpha)$, $\alpha$ is the rest of the stack ‘under’ $Z$; the statement says that if the automaton is in state $p$ with stack contents $Z\alpha$ (so that $Z$ is on the top of the stack), reading an input $aw$, it can make a direct transition to state $p$, reading an input $w$, with $\beta\alpha$ on the stack. In other words, it has read the single character $a\in\Sigma$, leaving as input the remaining string $w\in\Sigma^*$, it has popped the single character $Z\in\Gamma$ from the stack, leaving $\alpha\in\Gamma^*$ still on the stack, and it has pushed $\beta\in\Gamma^*$ onto the stack as well, so that the stack now contains the string $\beta\alpha\in\Gamma^*$.

Answer 2

$X \vdash Y$ means that if the automaton was in configuration $X$, then its next configuration will be $Y$.

$Z\alpha$ is the entire content of the stack. The idea is that the top stack symbol is $Z$, and the automaton can't see $\alpha$ because that is underneath. So it pops off the $Z$ and then supplies that as an argument to the transition function $\delta$. $\delta$ returns a new string of stack symbols, $\beta\in\Gamma^\ast$, and the automaton pushes the $\beta$ symbols onto the stack atop the $\alpha$ that were already there, leaving $\beta\alpha$ on the stack.

You didn't say what you mean $\Sigma$ and $\Gamma$ to be; I guess $\Sigma$ is the input alphabet and $\Gamma$ is the stack alphabet. In that case yes, we usually take $\Sigma$ to be a subset of $\Gamma$, which means that the automaton can remember input symbols by pushing them onto the stack. But that is just for convenience; if the stack and input alphabets were disjoint we could still have the automaton remember input symbols by encoding them as strings of stack symbols and pushing the codes on the stack.

Is $\dashv$ the special bottom-of-stack symbol? If so, then yes, $\dashv\not\in\Sigma$. Some books will take $\Gamma = \Sigma\cup\{\dashv\}$, but others will allow it to be bigger, or to be entirely disjoint from $\Sigma$; it doesn't matter very much in practice. You should consult your book to find out what your book says. You claim your book doesn't define these things, but I think you should look again.