特定のアルファベットにいくつの異なる遷移グラフがあるかをどのように判断しますか? たとえば、アルファベット {x, y} を超える TG の数。Daniel IA Cohen の著書「Introduction to computer theory」からの同様の質問のクラスを受講しています。TG を作成する方法の例はたくさんありますが、言語ごとに作成できる数を決定するものはありません。限られた量のTGを探していると思いますか？どうもありがとうございます！
1734 次
1 に答える
1
このような遷移グラフは数え切れないほど無数にあります。これについて考える 1 つの方法は、次のように、無限に多くの遷移グラフのファミリを簡単に構築できることです。固定された n (つまり、文字 a の n 個のコピー) に対して言語 a nを受け入れたいとします。次に、その言語を受け入れる遷移グラフを次のように作成できます。開始状態から開始し、n 個の新しい状態をその状態の最後に連鎖させます。それぞれの状態は「a」で次の状態に遷移します。最後の状態を受け入れます。
これらが数え切れないほど無限にあることを確認するために、これらのオートマトンをどのように説明するかを考えることができます。これを行うには、状態の数を単項で書き出し、次にそれらの状態間の遷移をタプル (開始、終了、文字) (すべてバイナリでエンコード) のリストとして書き出し、次に受け入れ状態を数のリストとして書き出します。単項状態。連結すると、これはバイナリ文字列であり、数え切れないほど多くの有限バイナリ文字列しかありません。
于 2011-07-25T03:09:48.267 に答える