正規文法よりもさらに複雑な文が書ける、文脈自由文法を見てみます。

文法のルールは正規文法と、さほど違わないのですが、カッコで再帰的に囲うような文が書ける ようになります。

そして、それをオートマトンで実現するのには、データを「スタック」とい う、一番最後の部分だけが読み書きできるようなものに書き込むことでできます。