アルファベットごとの遷移グラフ？

Question

特定のアルファベットに対していくつの異なる遷移グラフが存在するかをどのように決定しますか？たとえば、アルファベット{x、y}を超えるTGの数です。ダニエル・A・コーエンの本「コンピュータ理論の紹介」からも同様の質問で授業を受けています。 TGを作成する方法の例はたくさんありますが、言語ごとに作成できる数は決まっていません。私は有限量のTGを探していると仮定していますか？どうもありがとうございました！

Answer 1

無限に多くの遷移グラフがあります。これについて考える1つの方法は、次のように無限に多くの遷移グラフのファミリを簡単に作成できることです。いくつかの固定n（つまり、文字aのn個のコピー）に対して、言語ⁿを受け入れることを希望するとします。次に、その言語を受け入れる遷移グラフを次のように構築することができました。開始状態から始めて、その状態の終わりにn個の新しい状態を連鎖させます。それぞれの状態は、 'a'を次の状態に遷移させます。最後の状態を受け入れます。

これらの数え切れないほどのものが数多くあることを確認するために、これらのオートマトンをどのように記述するかを考えてみましょう。これを行うには、単項式の状態数を書き出し、それらの状態間の遷移をタプル（開始、終了、文字）（すべてバイナリでエンコードされたもの）のリストとして書き出し、次に受け入れ状態を単国の状態。一緒に連結された、これはバイナリ文字列であり、有限個の有限バイナリ文字列しか存在しません。