質問: 至急お願いします!! アルファベット ∑={a} 上の言語 L={a^(2n)|n≧1} を受理言語とするプッシュダウンオートマンの状態遷移図を描きなさいという問題です。 分からないので教えて頂きたいです!
回答: PDAじゃなくてFSAで十分。遷移図は面倒なんで遷移表で。 状態集合:{s0, s1, s2} 初期状態:s0 受理状態集合:{s2} 遷移表: s0, a→s1 s1, a→s2 s2, a→s1 どうしてもPDAじゃなきゃダメだってなら、スタックに触らなきゃいいんで、 遷移表: s0, a, ε→s1, ε s1, a, ε→s2, ε s2, a, ε→s1, ε