Um autômato de pilha é formalmente definido por uma sêxtupla:

M=(Q,\ \Sigma,\ \Gamma,\ \Delta, \ q_{0},\ F)

Onde:

  • \, Q é um conjunto finito de estados.
  • \,\Sigma é um conjunto finito de símbolos, denominado alfabeto de entrada.
  • \,\Gamma é um conjunto finito de símbolos, denominado alfabeto da pilha.
  • \,\Delta\subseteq (Q \times \Sigma^* \times \Gamma^*) \times (Q \times \Gamma^*) é a relação de transição.
  • \,q_{0}\in\, Q é o estado inicial.
  • F\subseteq Q é o conjunto de estados finais (ou de aceitação).

Um elemento (p,a,α,q,β) é uma transição de M. Ela significa que M, estando no estado p, com o símbolo a na cadeia de entrada e com o símbolo α no topo da pilha, pode consumir o símbolo a, transitar para o estado q e desempilhar α substituindo-o por β. O ∑* e o Γ* denotam o fecho de Kleene do alfabeto de entrada e da pilha, respectivamente. Portanto, estes componentes são utilizados para formalizar que o autômato de pilha pode consumir qualquer quantidade de símbolos da cadeia de entrada e da pilha.