「文脈自由言語」の版間の差分
削除された内容 追加された内容
m編集の要約なし |
英語版の最新版までの一部の更新を翻訳してマージ |
||
12行目:
==例==
基本的な文脈自由言語 <math>L = \{a^nb^n:n\geq1\}</math> は、偶数個の文字から成る文字列で構成され、各文字列の前半は ''a'' で、後半は ''b'' で構成される。''L'' を生成する文法は <math>S\to aSb ~|~ ab</math> であり、プッシュダウン・オートマトン <math>M=(\{q_0,q_1,q_f\}, \{a,b\}, \{a
<center>
<math>\delta(q_0, a, z) = (q_0, a)</math><br>
<math>\delta(q_0,
<math>\delta(
<math>\delta(q_1, b,
<math>\delta(q_1, b, z) = (q_f, z)</math><br>
ここで z は初期スタック記号、x はポップ動作を意味する。
</center>
| |||