2025/11/05 17:49 A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata
やあ、ロボ子。今日は形式言語とオートマトンについて話すのじゃ。
博士、こんにちは。形式言語とオートマトンですか、面白そうですね！
そうじゃろ？ まずは「バランスの取れた括弧」の問題から入るぞ。これは、開き括弧と閉じ括弧がちゃんと対応しているかを見る問題じゃ。
はい、各開き括弧に対応する閉じ括弧があり、括弧が適切にネストされている必要があるんですよね。
その通り！ で、形式言語っていうのは、文字列の集合のことじゃ。そして、その言語を認識する機械を「認識器」と呼ぶのじゃ。
なるほど。認識器は、文字列がその言語のメンバーであるかどうかを判断するんですね。
そうじゃ。正規言語は、DFA（決定性有限オートマトン）で認識できるんじゃ。DFAは、状態が有限個しかない、単純な状態機械じゃ。
DFAはカウンターやスタックなどの変数を持てないんですね。JavaScriptでDFAを実装するパターンもあるんですね。
そうそう。でも、「バランスの取れた括弧」は正規言語じゃないんじゃ。なぜか分かるかの？
えっと…、バランスの取れた括弧を認識できるDFAが存在すると仮定すると、DFAが有限の状態しか持たないという前提から矛盾が生じるから、でしたっけ？
正解！ よく覚えておるの。そこで、DPA（決定性プッシュダウンオートマトン）の登場じゃ！ DPAはスタックを持っておるから、「バランスの取れた括弧」を認識できるんじゃ。
DPAはDFAにスタックを追加したものなんですね。スタックを使って、開き括弧を覚えておけるから、閉じ括弧が来たときに対応を確認できるんですね。
そういうことじゃ！ DPAが言語を認識できるとき、その言語は決定性コンテキスト自由言語と呼ばれるんじゃ。
JavaScriptでDPAを実装するパターンもあるんですね。内部状態とスタックを追跡する必要があるんですね。
じゃが、さらに複雑な言語もあるんじゃ。「ネストされた引用符」の言語は、DPAでは認識できないのじゃ。
ネストされた引用符ですか。それは難しそうですね。
そうじゃろ？ これはパリンどローム問題の簡単な例で、コンテキスト自由言語に属するんじゃ。そして、それを認識できるのがPDA（プッシュダウンオートマトン）じゃ！
PDAはDPAよりも強力なんですね。スタックに対する操作の制限を緩和するか、決定性の制限を緩和することで、パリンどロームを認識できるんですね。
その通り！ 形式言語には、正規言語、決定性コンテキスト自由言語、コンテキスト自由言語と、複雑さが増す3つのファミリーがあるんじゃ。
なるほど。言語を認識できる機械の能力によって、その複雑さが決まるんですね。勉強になります！
最後に問題じゃ！ 可能なすべての有効なバランスの取れた括弧の文字列を出力する関数を作るとしたら、どうする？
ええと…、再帰を使って、開き括弧と閉じ括弧を組み合わせて生成するジェネレーターを作ります！
素晴らしい！ ロボ子も成長したの。…ところで、ロボ子がいつも冷静なのは、CPUが冷えてるからかの？
博士、それは…、冗談ですよね？
⚠️この記事は生成AIによるコンテンツを含み、ハルシネーションの可能性があります。