オートマトンについての問題

質問

提示された言語を受理するオートマトンを作成する問題を解いていたのですが、
いくつか分からないものがありました。
ご存知の方おられましたらご教授の程よろしくお願いいたします。

(1)L = {w | 2#a(w) = #b(w)} (ただし、#x(w) は w 中の x の個数を表わす。)
(2)L = {wcw | w ∈ Σ∗, c ∈ Σ}

(ここで、Σ = {a, b}であり、Σ∗はΣ上の全ての語の集合)

回答No.2

Tacosan

だとしたら, 「どれで受理できるのか」をまず判定しないとだめだね. 「どのオートマトンで受理できるのか」は実際に作ればいいだけだけど, 「これでは受理できない」というのは難しい....

ある言語が特定の種類のオートマトンで受理「できない」ことを示す方法として, 何を習いましたか?

いや, (1) はともかく (2) がどこまで「落とせる」か見えてないんだよね....

回答No.1

Tacosan

「オートマトン」といっても有限オートマトンやプッシュダウンオートマトン, あるいはチューリングマシンのようにいろんな種類があるわけですが, そのうちどれを使うんでしょうか?

補足

返答ありがとうございます。
種類についてですが、できるだけ能力が低いオートマトンで構築する必要があるようです。