有限状態マシンの定義と指定方法。 有限状態マシンの定義

それは明らかです k、r、sそれぞれ、数値の 2 進数表現の桁数に等しい t、p、r。たとえば、次の場合 た - 5, n= 17、p = 3、その後、k= 3、r= 5、s = 2。

2. ソースの入力および出力シンボルの状態のコーディング
機械。

各 q j Q 長さのバイナリシーケンスを 1 対 1 に対応させます。 r- バイナリ コード = z 1 z 2 z r . 同様に、各 a i X と b k Y について、バイナリ シーケンス =x 1 x 2 x k を 1 対 1 に対応させます。 =y 1 y 2 y s 。

状態、入力および出力シンボルのエンコードはさまざまな方法で実行できることに注意してください。 この場合、一部のシーケンス（コード）が未使用になる可能性があります。

3. 次の表を編集します。

この表には次のものが含まれます k + r + r + sコラムと 2k+r線。 まず最初に k+rすべての長さのセットが列にリストされています k+r。このような各セットはペア () に対応します。ここで、 はある状態の可能なコード、つまり入力シンボルのコードです。

4.テーブルの最後の列を入力します（前のステップ）。

各ペア (a i ,q j) について、a i X; q j Q , コードと を見つけます。 オートマトン テーブル (またはムーア図) を使用して \|/(a; q) = Y.次に、 code = "1" 2...",. と code を見つけます。

セットに対応する表の行へ

セットを追加する

5. ブール関数システムの定義。

前の手順を完了すると、テーブル内のすべての行が埋まっていることがわかります。 これは、数値 m、n の少なくとも 1 つが指定されている場合に発生します。 は 2 の累乗ではありません。したがって、関数は完全には定義されません。一部のセットでは値が定義されていません。 次に、それらを任意の方法で定義します。 原則として、関数は、結果として得られる完全に定義された関数が特定の最適性条件を満たすようにさらに定義されます。たとえば、関数は最小限の DNF で表されます。

このステップを完了すると、完全に定義されたブール関数のシステムによって元のオートマトンが指定されます。

3.2 初心者向け言語.

これらはオートマトンを行動レベルで記述します。 主な言語には次のものが含まれます。

1) 論理回路の言語とアルゴリズムのグラフ図。

2) イベント代数の正規表現の言語。

3) 形式文法とオートマトン文法。

完全に定義されたオートマトンの記述 (4) が標準形式で与えられる場合、オートマトンの初期状態に対して s(0) および入力文字のシーケンス v(0)v(1)v(2)…v(t) 一連の出力シンボルの形式でマシンの応答を計算できます。 w(0)w(1)…w(t).

例。

例1。 新聞「SELLER」は、1 ルーブルと 2 ルーブルの硬貨を受け取ります。 コインの量が 3 ルーブルに等しい場合、機械は新聞を発行します。 金額が3ルーブルを超える場合、機械は全額を返します。 入出力シンボルの名称とマシンの状態を紹介します。

入力文字:

v 1 - 1 ルーブル コインがドロップされます。

v 2 - 2 ルーブル相当のコインがドロップされます。

出力文字:

w 1 - メッセージ「1 ルーブルの金額が受け入れられました。」;

w 2 - メッセージ「2 ルーブルの金額を受け入れます。」;

w 3 - 新聞配達。

w 4 - 返金。

マシンの状態:

s 0 - 許容量は 0 こすりです。 (初期状態);

s 1 - 許容量は 1 こすりです。

s 2 - 受け入れ金額は2ルーブルです。

遷移関数を表 2 に、出力関数を表 3 に示します。

同じオートマトンは、マークされた有向グラフの形式で指定できます。その頂点はオートマトンの状態に対応し、円弧は遷移に対応します (図 3)。

以下は、入力シーケンスに対する SELLER マシンの応答の例です。 v 1 v 1 v 2 v 2 v 1 v 2 v 2 v 1 v 1 v 1 …:

例2。上記で検討した SELLER マシンの場合、遷移/出力のテーブル (表 4) を特徴とする同等の Moore マシンを構築することが可能です。

表4

図 4 は、表 4 に対応する SELLER マシンの遷移/出力グラフを示しています。 同等のムーア マシンの初期状態には、入力シンボルが含まれます。 v(0)。 したがって、入力シンボルのストリームをシフトする必要があります。

息子を学校に通わせた親の行動を説明してみましょう。 息子は二と五を持ってきます。 父親は息子がまた悪い点を取るたびにベルトを掴むことを望まず、より巧妙な子育て戦略を選択している。 頂点が状態に対応するグラフによってオートマトンを定義すると便利です。状態 s から状態 q へのエッジ (x/y とラベル付け) は、入力信号 x の影響下で状態 s からのオートマトンが描画されるときに描画されます。 、出力反応 y を伴う状態 q に移行します。 親の賢い行動をモデル化したオートマトンのグラフを図に示します。 5.

米。 5.「賢い」父親の行動を記述するオートマトン

このオートマトンには 4 つの状態 (s0、s1、s2、s3) と 2 つの入力信号 (息子が学校で受けた成績: (2.5)) があります。 初期状態 s0 (入力矢印で示されている) から始まり、マシンは入力信号の影響を受けて、ある状態から別の状態に移動し、入力に対する反応である出力信号を生成します。 次のように、マシンの出力 (y0,..., y5) を親のアクションとして解釈します。

y0: - ベルトを取る。

イル: - 息子を叱ってください。

y2: - 息子を安心させてください。

UZ: - 希望です。

y4: - 喜ぶ。

y5: - 喜ぶよ。

同じ成績（D）を受けた息子は、勉強の背景に応じて、家庭での父親の反応がまったく異なります。 父親は息子が以前どのように勉強したかを思い出し、以前の成功と失敗を考慮して息子のしつけを構築します。 たとえば、ストーリー2、2、2の息子は3回目のデュースの後、ベルトを持って迎えられ、ストーリー2、2、5、2では彼らは落ち着きます。 各履歴はオートマトンの現在の状態を決定しますが、一部の入力履歴は同等です (つまり、オートマトンを同じ状態にするものです)。履歴 2、2、5 は空の履歴に相当し、初期状態に対応します。

オートマトンの現在の状態は、オートマトンが将来の動作、つまり後続の入力に対する反応に関して過去について知っていることすべてを表します。 この集中的な形式の履歴は現在の状態によって決定され、その後の入力信号に対するマシンの反応としてのマシンの将来の動作全体が決定されます。 正確には現在の状態ではありますが、マシンがどのようにしてその状態に至ったかではありません。

したがって、有限状態マシンは、離散時間 (サイクル) で動作するデバイスです。 各クロック サイクルで、考えられる入力信号の 1 つが有限状態マシンの入力で受信され、現在の状態と受信した入力信号の関数である出力信号が出力に表示されます。 機械の内部状態も変化します。 動作の瞬間（サイクル）は、強制クロック信号によって、または外部イベントの発生、つまり信号の到着によって非同期的に決定されます。

有限オートマトンを形式的に定義してみましょう。

マシンのグラフィック表現に加えて、テーブル形式で遷移と出力の機能を指定する表形式の表現も使用できます。 マシン例は次の表で表されます。

表5 あ遷移関数を次のように定義します。

そしてテーブル 5、b は出力の関数を定義します : .(s0, 2) = y2; (s2, 5) = y3; ....

有限オートマトンの表現は、実際には、それを定義するオートマトン関数の記述に帰着します。

有限状態マシンを定義するには 3 つの方法があります。

· 表形式 (遷移と出力のマトリックス)。

· グラフィック (グラフを使用);

· 分析的 (数式を使用)。

分析方法– オートマトンは連立方程式によって指定されます。 このようなシステムから、可能な内部状態の数が有限であるため、オートマトン関数の可能な値の数も有限であることがわかります。 このようなタスクの例としては、Mealy オートマトンと Moore オートマトンを定義する方程式系があります。

表形式の方法。マシンの状態テーブルは、遷移関数 – δ と出力関数に対して編集されます。 この場合：

· テーブルの列は入力アルファベットの要素に対応します ×、

· テーブルの行は状態 (有限集合の要素) に対応します。 質問）。

i 行目と j 列目の交点はセル (i, j) に対応します。これは、オートマトンが次の状態にある瞬間の関数 8 と λ の引数です。 qi入力には単語があります xj、そして最も適切なセルに関数8とλの値を書き込みます。 したがって、テーブル全体が集合に対応します。 Q× X.

遷移テーブルに記入するとき、各セルは、次の状態のシンボルと出力信号のシンボルのペアのシンボルによって一意に識別されます。

実際には、オートマトン関数は、それぞれ呼ばれる 2 つの有限テーブルによって指定されます。 遷移行列そして 出力行列。 この場合、行は入力アルファベットの文字で指定され、列は内部アルファベット (マシンの内部状態をコード化する記号) の文字で指定されます。

遷移行列では、行 x k と列 q r の交点で、遷移関数 δ(q i, X)および出力関数 λ(q, X)。 場合によっては、両方のテーブルが 1 つのテーブルに結合されることがあります。

グラフィックメソッド。

オートマトンは、グラフ、ダイアグラム、グラフなどを使用して指定されます。有向グラフを使用して指定することは、オートマトンを記述するより便利でコンパクトな形式です。

オートマトングラフ含まれています

· ピークス、条件に応じて qiÎQ、

· アーク、接続頂点は、オートマトンのある状態から別の状態への遷移です。 入力信号と出力信号のペア (遷移信号) を円弧上に示すのが一般的です。

マシンがその状態から外れてしまった場合 q1状態で q2いくつかの入力信号の影響下では、グラフの対応する円弧上で、このオプションは論理和によって表されます。 オートマトンを表現するには、区別された初期状態と最終状態を持つ 2 極グラフが使用されます。

「静電容量を測定する装置」用スケールを開発

図2.5。 静電容量測定器のスケールグラフ

結論

高周波発振を発生させるための発振回路（RC 型）を備えた発電機の使用では満足できないため、開発中の発電機には LC 型回路が採用されました（単巻変圧器結合を備えた 3 点回路が位相チェーンとして採用され、能動素子はトランジスタです）。

このコースワークの理論的な部分では、LC タイプの発電機の要素が考慮されました。 LC 型発電機の分類とその目的、さまざまな発電回路についても検討しました。 発電機要素の技術的特徴も同様です。

実践編では、エンコーダ、デコーダとその目的について説明し、エンコーダとデコーダの電気機能図、電気回路図を設計しました。 カルノー図の話題が明らかになりました。 7 セグメント指標の「b」セグメントも開発されました。 静電容量を測定する装置の規模に合わせて有限状態マシンとそのグラフを開発しました。

基本定義 n 有限オートマトンはシステム M =(A, B, S, y) であり、n n n A = (a 1, ..., am) は有限入力アルファベット、B =(b 1, ... , am) です。 . , bk ) - 最終出力アルファベット、S =(s 1, . . . , sn) - 状態の最終アルファベット、: A S S - 遷移関数、y: A S B - 出力関数。 n オートマトン M で初期状態と呼ばれる 1 つの状態が選択された場合 (通常、これは s 1 であると想定されます)、結果のオートマトンは初期状態と呼ばれ、(M, s 1) と表されます。 n オートマトンを定義するには 2 つの方法があります: オートマトン テーブル、遷移図

自動テーブル n 1) 2) 3) 4) 例: 入力文字が「0」と「1」の場合、単語「001」を読み取るようにオートマトンを設定します。 入力アルファベット A=(0, 1) 出力アルファベット A=(Y, N) 状態アルファベット S=(s 0 "", s 1 "0", s 2 "00" s 3 "001") 2 通りの自動テーブル。 は、1) ライン – マシンの状態によって指定されます。 列は入力記号です。 行と列の交差点に、関数 y が示されます。 2) S、A、y を列で指定します。 演習 25 単語 KAKADU SA 0 1 S 0 "" S 1, N S 0, NS S 1 " 0" S 2, N S 0, NS S 2 " 00" S 2, N S 3, Y S 3 " 001 を検索するオートマトンを構築する" S1、NS0、NSInyS00S1N1S0N0S2N1S3Y0S1N1S0NS1S2S3

遷移図 n グラフと呼ばれる指向性遷移図はマルチグラフであり、遷移またはグラフは状態に対応します。 (Si, aj)=Sk、y(Si, aj)=bl の場合、頂点 Si から頂点 Sk まで円弧が描かれ、その上に (aj, bl) n と書かれます。各頂点 si での正確性の条件は次のとおりです。 0 1 S 0 "" S 1、NS 0、NS 1 « 0» n 頂点、y S 2、NS 0、NS 2 « 00» S 2、NS 3、YS 3 « 001» S 1、NS 0、N 1、 N は満たされます。 1) 任意の入力文字 aj に対して、si から伸びる弧があり、その上に aj が書かれます (完全性条件)。 2) 任意の文字 aj は、si から出てくる 1 つのエッジにのみ出現します (一貫性または決定性条件) S 0 S 1 (0, N) (1, N) (0, N) (1, N) S 2 (1, Y )S3

オートマトンと入力語 n 与えられたオートマトン M の場合、その機能は M と y です。 M は、すべての入力文字の集合 A だけでなく、すべての入力単語の集合 A* でも定義できます。 n 任意の入力単語に対して = aj 1 aj 2。 。 ajk (si, aj 1 aj 2. . . ajk) = ((… (si, aj 1), aj 2), . . . , ajk-1), ajk)。 y (si, aj 1 aj 2... ajk) = y((... (si, aj 1), aj 2),... , ajk-1), ajk)。

例: オートマトンと入力単語 例: = 0101 (S 1, 0101) = ((S 1, 0), 1) (S 1, 0101) = (((S 2, 1), 0), 1) (S 1, 0101) = ((S 3, 0), 1) (S 1, 0101) = (S 1, 1) (S 1, 0101) = S 0 0 1 S 0 "" S 1, NS 0, NS 1 " 0" S 2, N S 0, NS 2 " 00" y(S 1, 0101) = y((((S 1, 0), 1) y(S 1, 0101) = y(((S 2 、1)、0)、1) y(S 1, 0101) = y((S 3, 0), 1) y(S 1, 0101) = y(S 1, 1) y(S 1, 0101) = N、y S 2、NS 3、YS 3 “001” S 1、NS 0、N

自動マッピング n M の初期状態 S 0 と各入力単語 = a 1 a 2 を固定しましょう。 。 ak 出力アルファベットの単語と一致します: = y (S 0, a 1) y(S 0, a 1 a 2)。 。 。 y(S 0, a 1... ak)。 (3 a) n 入力単語を出力単語にマッピングするこの対応は、オートマトン マッピングと呼ばれます。 n 単語に演算子を適用した結果が出力単語である場合、これをそれに応じて M() = と表します。

例: 自動マッピング 入力単語 = 0101 を出力アルファベットの単語と照合します: = y (S 0, 0) y(S 0, 01)y(S 0, 0101)。 y (S 0, 0)= N , y 0 S 0 "" S 1、NS 0、NS 1 "0" S 2、NS 0、NS 2 "00" S 2、NS 3、Y 1 S 3 " 001 » S 1, N S 0, N y(S 0, 01) = y((S 0, 0), 1) = y(S 1, 1) = N y(S 0, 010) = y(((S 0, 0), 1), 0) = y((S 1, 1), 0) = y(S 0, 0)=N y(S 0, 0101) = y((((S 0, 0) , 1) =y(((S 1, 1), 0), 1) = = y((S 0, 0), 1) = y(S 0, 1) = NNNN

自動マッピングのプロパティ 1) 単語と = M() は同じ長さです。 | = | | (長さ保存特性); 2) = 1 2 および M(1 2) = 1 2 の場合、ここで | 1| = | 1| の場合、M(1) = 1; 言い換えれば、長さ i のセグメントの画像は、同じ長さの画像のセグメントと等しいです。

オートマトンの種類 前述した有限オートマトン (S-finite) の一般的なモデルは、Mealy オートマトンと呼ばれます。 n オートマトンは、入力アルファベットが A = (a) という 1 つの文字で構成されている場合、自律的と呼ばれます。 自律オートマトンのすべての入力単語は aa の形式をとります。 。 。 A. n 有限オートマトンは、出力関数が状態のみに依存する場合、つまり任意の s、ai、aj y(s, ai) = y(s, aj) に依存する場合、ムーア オートマトンと呼ばれます。 ムーア マシンの出力関数は当然、引数が 1 つです。 通常は文字で表され、マーク関数と呼ばれます。 ムーア マシンのグラフでは、出力はエッジではなく頂点に書き込まれます。

ムーア オートマトンの定理: あらゆる Mealy オートマトンには、同等の Moore オートマトンが存在します。 n オートマトンの機能を調べる場合は、ムーア オートマトンを使用するだけで十分です。 これは、ムーア オートマトンを出力のないオートマトンとして見ることができ、その状態がさまざまな方法でマークされるため便利です。

自律オートマトンの例 SA a S 1 S 3.0 S 2 S 4.0 S 3 S 4.0 S 4 S 7.0 S 5 S 4.2 S 6 S 5.0 S 7 S 6.1 S 8 S 9, 0 S 9, 1 S S S S S A=(a) 、B=(0、1、2)、S=(S1、S2、S3、S4、S5、S6、S7、S8、S9)

区別できない状態 n M と T を、入力および出力のアルファベットが同一である 2 つのオートマトンとします。 オートマトン M の状態 s とオートマトン T の状態 r は、どの入力単語でも M(s,) = T(r,) の場合には区別できないと言われます。 オートマトン M の任意の状態 s に対してオートマトン T の区別できない状態 r が存在し、逆に、T の任意の r に対して M と区別できない状態 s が存在する場合、n オートマトン M と T は区別できないと呼ばれます。 n 区別できない状態は、と呼ばれます同等

最小オートマトン n オートマトン M から等価オートマトンへの遷移は、オートマトン M の等価変換と呼ばれます。 n 与えられたオートマトンと等価で与えられた特性を持つオートマトンを見つけることに関して、さまざまな問題を提起することができます。 このような問題の中で最も研究されているのは、オートマトンの状態数を最小化する問題です。M に相当するオートマトンの中から、状態数が最小のオートマトン、つまり最小オートマトンを見つけます。

オートマトンの「作業」の側面 オートマトンの「作業」には、主に 2 つの側面が区別されます。 1) オートマトンは入力単語を認識します。つまり、入力として与えられた単語が所定のセットに属するかどうかという質問に答えます (これらは、オートマトン認識装置です)。 2) オートマトンは入力単語を出力単語に変換します。つまり、オートマトン マッピング (自動コンバータ) を実装します。

メタ数学の枠組みにおける TA n メタ数学の枠組みにおけるアルゴリズムと形式システムの理論の主題 - どのオブジェクトとそのアクションが正確に定義されているとみなされるべきか、基本的なアクションの組み合わせにはどのような特性と機能があるか、何が可能で何が不可能か彼らの助けで完成しました。 n アルゴリズム理論の主な応用は、特定の数学的問題に対するアルゴリズムによる (つまり、正確で明確な) 解決策が不可能であることを証明することです。

アルゴリズム n アルゴリズムは、ソース データを必要な結果に変換するプロセスを一意に指定する処方箋です。 n 変換プロセス自体は、基本的な個別のステップで構成され、有限回の適用によって結果が得られます。

アルゴリズムの主な種類 n アルゴリズム理論は、アルゴリズムのさまざまな (定性的および定量的) 特性を研究するメタ理論です。 n 定性的特性を研究するために、3 つの主なタイプのアルゴリズムが定義されます: 1) 再帰関数、2) チューリング マシン、3) 正準ポスト システムおよび通常のマルコフ アルゴリズム。

最も単純な再帰関数 n S 1(x) = x+1 - この関数は 1 つの変数 x に依存し、x+1 に等しくなります。 n On(x 1…xn) =0 - n 個の変数に依存し、常に 0 に等しい関数。 n Imn(x 1…xn) = xm - n 個の変数に依存し、常に変数 xm の値に等しい関数。

原始再帰 n 関数 f(x 1…xn+1) は、関数 g(x 1…xn) と h(x 1…xn+2) から原始再帰アルゴリズムによって取得されます (f(x 1, …xn) , 0) = g (x 1, …xn) (1) f(x 1, …xn, y+1) = h(z)、z=f(x 1, …xn, y) (2) 関数f は、最も単純な関数 S 1、On、Imn から有限数の重ね合わせ演算と原始再帰演算によって取得できる場合、原始再帰と呼ばれます。

例 n 関数が基本的に再帰的であることを証明するには、次のことが必要です。 1) 式 (1) および (2) に従って、関数 g() および h() を明示的に定義します。 2) g() と h() が最も単純な関数 S 1、On、Imn、または以前に証明された原始再帰関数であることを示します。 演習 26: 関数 f(x, y) = x+y が原始再帰的であることを証明する チャーチの命題: アルゴリズムで計算可能な数値関数のクラスは、すべての再帰関数のクラスと一致します。

チューリング マシン n チューリング マシンには以下が含まれます。 n 1) 外部メモリ – n 個のセルのテープ。 各 i 番目のセルは状態 ai にあります。 州のアルファベットが指定されます。 テープは両方向にエンドレスにすることができます。 空の状態は省略されます。 n 2) マシンの内部メモリ - デバイスは現在 qi 状態にあります。 内部状態のアルファベットを指定します。 初期状態 q 1、最終状態 q 0 または qz。 n 3) ポインタ – 現在のセルを指し、テープに沿って移動します。 n 4) 制御デバイス – ポインタが指すセルのシンボルを読み取ります。 プログラムに従ってセルの状態を変更し、ポインタを移動します。

状態とプログラム MT n チューリング マシンの状態はワード n n n n n a 1…ak-1 qi ak…ar と呼ばれ、観察されるセルの前に内部状態記号を挿入することによって形成されます。 チューリング マシン プログラムは、マシン qi aj qi' aj' D が実行できる一連のコマンドです。ここで、qi はマシンの内部状態、aj は監視されているセルの状態、qi' はマシン aj の新しい状態です。 ' は監視対象のセルに書き込まれる新しいシンボルです D = ( L, R, E) – ポインタが 1 セルずつ左、右にシフトすること、およびシフトしないことを象徴するシンボルです。

MT の例 演習 27: チューリング マシンの最終状態を求める 初期アルファベット: A = (0, 1) 内部状態アルファベット: Q = (q 0, q 1, q 2) プログラム: ( 1) q 10 q 20 R, 2)q 20 q 01 E、3) q 11 R、4) q 21 R ) 開始単語: q 111

例 MT 演習 28 チューリング マシンの最終状態を求める 初期アルファベット: A = (0, 1, ) 内部状態アルファベット: Q = (q 0, q 1, q 2, q 3) プログラム: ( 1) q 1 q 00 R、2) q 11 q 20 R、3) q 21 R、4) q 2 q 31 L、5) q 30 q 00 R、6) q 31 L ) A) 最初の単語: q 111 1 B) イニシャル単語: q 11 111

チューリングの理論 チューリングの理論: アルゴリズム A ごとにチューリング マシンを構築できます。同じ初期データが与えられると、アルゴリズム A と同じ結果が得られます。 n 1 q 1 2 1 qz 2 の場合、マシン T は処理を行うと言えます。 word 1 2 を word 1 2 に変換し、それを T(1 2) = 1 2 と表します。 n 表記 T() は、元の値を持つマシン T の指定です。

正規マルコフ アルゴリズム n 正規マルコフ アルゴリズム (NAM) は、置換を使用して有限長の単語を相互に変換します。 n タスク NAM のアルファベット置換 u v 最終置換 u v n 演習 29 通常のマルコフ アルゴリズムが与えられます。 アルファベット - ロシア語のアルファベット。 置換スキーム (Y U、L U、S M、V B、RT、TR、OX、NA) n 最初の単語 ELEPHANT。 n 最後の単語を見つけます。

アルゴリズム n の複雑さの推定 関数 f(n) と g(n) が 2 つのアルゴリズムの効率を測定すると仮定します。これらは通常、時間計算量関数と呼ばれます。 | 次のような正の定数 C がある場合、関数 f(n) の成長の次数は g(n) の成長の次数よりも大きくないと言うでしょう。 f(n) |

アルゴリズムの効率 A B C D E n 3 n 2 2 n 2+4 n n 3 2 n 1 1 ms 3 ms 6 ms 2 ms 10 10 ms 300 ms 240 ms 1,024 s 100 ms 30 s 20.4 ms 0.28 h 4*1017 世紀 0.56 時間 11. 6日 10176 世紀 1000 ミリ秒 0.83 時間 1 ミリ秒

アルゴリズムの理論 n アルゴリズムの理論 - 問題を複雑さによって分類します。 この場合、認識タスクのみが分類されます。 n 認識タスクは、入力データに何らかのプロパティがあるかどうかという質問に答えるタスクです。 私たちの場合: 入力データ - グラフ、プロパティ - グラフはハミルトニアンですか?

クラス P および NP n 複雑度クラス P: 問題を多項式時間で解くアルゴリズム A があります。 n 複雑さクラス NP - 提案された解を多項式時間でチェックするアルゴリズム A があります。 n ハミルトニアン サイクル問題は、指定されたグラフ G がハミルトニアン サイクルを持ち、NP クラスに属するかどうかを調べることで構成されます。

NP 問題の例 n ブール関数の充足可能性問題: 指定されたブール式を使用して、その式にそれを 1 にする変数のセットが含まれているかどうかを調べます。 n クリーク問題: 指定されたグラフを使用して、そのグラフに含まれているかどうかを調べます。指定されたサイズのクリーク (完全なサブグラフ)。 n グラフ内のハミルトニアン サイクルの存在の問題。 n 線形不等式系に対する整数解の存在。

NP 問題を総当たりで解決できる可能性 n 最初は、解決策はわかりません。 したがって、NP クラスに属する問題はすべて、考えられるすべての組み合わせ n を探索することによって指数関数的時間で解決できることが重要であることがわかります。これが、ハミルトン サイクルを見つけるアルゴリズムで起こることです。

P と NP の関係 n P からのすべての問題は NP に属します。 n したがって、クラス NP にはクラス P が含まれます。現時点では、クラス P と NP が同じかどうかは不明ですが、ほとんどの専門家はそれらが同じではないと考えています。

P と NP の関係 n P = NP であることが判明した場合 1) NP 問題は妥当な時間内に解決できるでしょう。 2) 指数関数的な複雑さの問題を意図的に使用する (つまり、問題が解決できないと仮定して) 問題が多数あります。 たとえば、暗号学には公開キー暗号化に関するセクションがありますが、これを復号化することは事実上不可能です。 突然 P = NP になった場合、多くの秘密はそのようなものではなくなります。

NP 完全問題 n P ≠ NP を信じる最も深刻な理由は、NP 完全問題の存在です。 n 非公式に!!! 他の入力に対する問題 Q' の解が既知であると仮定して、問題 Q が任意の入力に対して多項式時間で解ける場合、問題 Q は問題 Q' に帰着します。 たとえば、一次方程式を解く問題は、二次方程式を解く問題に還元されます。

NP 完全問題 n NP 完全問題は、クラス NP からの他の問題を帰着できるクラス NP からの問題です。 n NP 完全問題は、NP クラスの「最も難しい」問題のサブセットを形成します。 NP 完全問題に対して多項式解法アルゴリズムが見つかった場合、NP クラスの他の問題は多項式時間で解くことができます。 n リストされているすべての NP 問題は NP 完全です。 ハミルトンサイクルの問題も含めて。

バラノフ・ヴィクトル・パブロヴィチ。 離散数学。 セクション 6. 有限オートマトンと形式言語。

講義 31. 有限状態マシンの定義と指定方法。 合成タスク。 初級オートマトン

講義 30. 有限機械の定義と指定方法。

合成の問題。 基礎機械

講義概要：

1. 有限状態マシンの定義。

2. 有限状態マシンを指定する方法。

1. オートマトンの合成問題。
2. 初歩的なオートマトン。
3. オートマトン基盤の完全性の問題。
4. オートマトンを合成するための標準的な方法。

1. ステートマシンの定義

SFE は、実際のデバイスが時間の経過とともに動作するという事実を考慮していません。 SFE と比較して、有限状態マシンは離散情報コンバータのより正確なモデルです。 同時に、有限オートマトンの概念は、他のモデルと同様に、単純化するための多くの仮定に関連付けられています。

まず、各瞬間におけるマシンの入力と出力は、有限数の異なる状態のうちの 1 つだけになり得ると想定されます。 実際のコンバーターに連続入力信号がある場合、有限状態マシンを使用してそれを記述するには、この信号を量子化する必要があります。 オートマトンの正式な定義では、オートマトンの入力状態と出力状態の有限セットはそれぞれ入力アルファベットと出力アルファベットと呼ばれ、個々の状態はこれらのアルファベットの文字と呼ばれます。

第二に、時間は離散的に変化すると仮定します。 入力状態と出力状態は離散時間シーケンスに対応します。時間の瞬間はそのインデックスによって一意に決定されるため、簡単にするために、時間は 1、2、... の値を取ると仮定します。この時間間隔はティックと呼ばれます。

機械の動作は次のように表されます。

マシンの入力は入力アルファベットから信号を受け取り、これにより出力に入力アルファベットからの信号が現れます。 入力に対する出力シーケンスの依存性は、マシンの内部構造によって異なります。 メモリを持たない SFE とは異なり、オートマトンはメモリを持つデバイスであることに注意してください。つまり、オートマトンの出力は入力だけでなく履歴によっても決定されます。 履歴は、入力だけでなく、現在の状態にも依存する出力信号によって実行されることを考慮します。

オートマトンの正式な定義を与えてみましょう。

有限状態マシンは 5 つのオブジェクトから構成されます。

入力アルファベットと呼ばれる有限集合。 可能な入力状態の 1 つ。

出力アルファベットと呼ばれる有限集合。 このセットの要素によって、可能な出力状態が決まります。

内部状態のアルファベットと呼ばれる有限集合。

マシン遷移の関数: ; この関数は、各「入力状態」ペアに状態を割り当てます。

マシン出力の関数: ; この関数は、各入力状態ペアに出力値を割り当てます。

オートマトンの動作の法則: オートマトンは機能に従って状態を変更し、機能に従って出力信号を生成します。

1. 有限状態マシンを指定する方法

1. 表形式の割り当て方法。 関数の場合、定義領域と値の両方が有限集合に属するため、テーブルを使用して指定されます。

例 1. オートマトンを次のように定義します。 、 。遷移テーブルを使用して関数を定義し、出力テーブルを使用して関数を定義します。

表 1. 遷移表 表 2. 出力表

マシンの入力における信号のシーケンスが既知の場合、出力シーケンスは遷移と出力のテーブルによって一意に決定されます。

2. グラフィックによる割り当て方法。 遷移出力図が使用されます。 これは、オートマトンの各内部状態が頂点に対応する指向性マルチグラフです。 オートマトンの状態から状態への遷移は矢印で示されており、それぞれの矢印上に、この遷移を引き起こす入力シンボルとオートマトンによって生成される出力シンボルが書かれています。

図1 遷移出力図

例 2. 次のように動作するオートマトンを構築する必要があります。各クロック サイクルで、項の次の 2 進数がオートマトンの入力で受信され、オートマトンはそれらの合計の対応する 2 進数を生成します。 2 桁の項の場合、次のようになります。

前のビットを追加するときにキャリーが発生した場合、マシンは状態 1 になり、それ以外の場合は状態 0 になります。 遷移出力図を図に示します。 2.

1. オートマトン合成問題

SFE の合成問題と類推すると、オートマトンの合成問題を提起できます。 基本マシンのセットは無制限です。 所定の機能を持った自動機械を組み立てる必要があります。 この場合、合成タスクは特定の問題に直面します。

マシンの出力をマシンの入力に接続する必要があると仮定します。 これは、そうでないと 2 番目のマシンが最初のマシンからの信号を理解できないという条件下で可能です。 これにより、一部の接続が不可能になるという混乱した状況が発生します。

この障害を克服するために、すべてのアルファベット (入力、出力、内部状態) がバイナリ ワードでエンコードされる構造オートマトンの概念が導入されます。

を要素の有限集合とし、長さのバイナリワードの集合とする。 バイナリワードによるセットのエンコードを任意の単射写像と呼びます。

任意のオートマトンのアルファベットをエンコードしてみましょう。

ある時点での、エンコードされた入力、出力、およびマシンの状態をそれぞれ表します。 次に、動作法則は次の形式で表示されます。

コーディング後に得られるオートマトンは構造的と呼ばれます。 構造オートマトンにはバイナリ入力、バイナリ出力があり、オートマトンの内部状態は長さのバイナリ ワードによって指定されると仮定します。 図では、 図 3 は、抽象オートマトンとそれに対応する構造オートマトンを示しています。

構造オートマトンへの移行は、合成に 2 つの重要な利点をもたらします。

1. バイナリ情報が入力と出力を介して送信されるため、入力と出力の互換性。 構造オートマトンの回路の一般的な定義は説明しません。これは SFE に似ています。

2. 関係式 (2) を「座標」に書きます。

(3) から、構造オートマトンの機能の法則はブール関数のシステムによって与えられることがわかります。

1. 初級オートマトン

最も単純な構造オートマトンを特定し、名前を付けてみましょう。

まず、状態が 1 つだけある機能要素は、記憶を持たないオートマトンとみなすことができることに注意してください。

2 つの状態を持つオートマトンに移りましょう。 マシンに、内部状態と一致する 1 つのバイナリ入力と 1 つのバイナリ出力があるとします。

図に示すマシンを指定するには、 4、遷移テーブルのみを設定するだけで十分です。

表3

アスタリスクの代わりに、0 と 1 を入力する必要があります。これは 16 通りの方法で実行できますが、すべてが受け入れられるわけではありません。 たとえば、表 3 の最初の列で両方の要素がゼロであると仮定します。 このようなオートマトンは、一度状態 0 になると、そこから抜け出すことはありません。つまり、機能要素として機能します。 同様の状況を分析すると、記憶のないオートマトンに還元できないオートマトンを取得するには、表 3 の各列に 0 と 1 の両方が含まれる必要があることがわかります。 このようなテーブルは 4 つだけです。

表4 表5

表6 表7

内部状態を反転すると 4 から 7 が得られ、5 から 6 が得られるため、最も単純なオートマトンは 2 つだけです。

表 4 で指定されたマシンは、遅延またはトリガーと呼ばれます。

つまり、このマシンは信号を 1 クロック サイクル遅らせます。

表 5 で指定されるマシンは、カウント入力付きトリガーまたは -トリガーと呼ばれます。 入力で 1 を受信するとマシンの状態は反転し、入力で 0 を受信すると変更されません。

-trigger が最初の時点で状態 0 であるとします。ある時点で -trigger が状態 0 にある場合、これは偶数の 1 がマシンの入力に到着したことを意味します。 状態が 1 の場合は奇数です。 したがって、フリップフロップは入力で 1 の数を数えますが、状態が 2 つしかないため、最大 2 までカウントします。

トリガーを物理的に実装する場合、ダイレクト出力とインバース出力の 2 つの出力が使用されます (図 5)。 これらを入れ替えると、-trigger は表 7 で指定されたオートマトンを生成し、-trigger は表 6 で指定されたオートマトンを生成します。

1. オートマトン基盤の完全性の問題

構造オートマトンのセットは、それらから所定の構造オートマトンを構築できる場合、完全 (またはオートマトン基礎) と呼ばれます。

オートマトン用のポストの定理の類似物を得ようとする数学者の努力は失敗に終わりました。 1964 年に、M.I. システムの完全性を判断するアルゴリズムが存在しないことが簡単に証明されました。 この場合、システムに関する追加の仮定を備えた完全性定理の変形が興味深いものになります。 その中で最も人気のあるものを見てみましょう。

定理。 FE と -trigger (または -trigger) の完全なセットを含むオートマトンのシステムが完成します。

証拠。 関係式 (2) で指定される任意のオートマトンを考え、その回路を指定されたオートマトンから正準構造と呼ばれる回路で記述します (図 6)。

このスキームは 2 つの部分で構成されます。

左半分は収納部と呼ばれます。 これはトリガーで構成され、その一連の状態がマシンの状態を形成します。

これは、マシンがその状態にあることを意味します。

右半分は組み合わせ部分と呼ばれ、SFE を表します。 この回路の入力:

1. マシンのバイナリワード入力信号。
2. バイナリ ワード マシンの現在の内部状態。

1. マシンのバイナリ ワード出力信号。式 (3) に従って実装されます。
2. 記憶部のフリップフロップの入力に到着し、マシンのメモリを制御するバイナリ ワード。

メモリ制御信号はマシンの出力と同じ変数のブール関数であるため、完全な FE システムによって実装できることを示しましょう。

あらゆる瞬間に、メモリ制御信号がマシンを状態から状態に転送する必要があります。 これを行うには、各トリガーの状態を変更する必要があります

正規回路で使用される -flip-flops または -flip-flops には次の特性があります。どの状態のペアにも、オートマトンを状態から状態に転送する入力信号があります。 この信号を で表しましょう。 -フリップフロップの場合、 -フリップフロップが設定される状態は入力信号と等しいため。 トリガーの場合: 状態が変化しないように、入力時に 0 を適用する必要があります。 1 に設定すると、トリガーが「反転」します。

つまり、ベクトル形式で

オートマトンの動作法則(2)から表現してみましょう。 それから

定理は証明されました。

1. オートマトンを合成するための標準的な方法

具体的な例を使用してこの方法を見てみましょう。

例。 2 種類の部品が移動するコンベア上には自動機械が設置されており、この機械の役割は、機械を通過した後に部品がグループになるように仕分けすることです。 機械は不適切な部品をコンベアから押し出します。 このようなオートマトンの回路は、トリガと「AND」「OR」「NOT」の要素を使って構築する必要があります。

オートマトンの合成は次の段階に分かれています。

1. 抽象オートマトンの構築。

アルファベットを入力してください。 出力アルファベットは です。ここで、C はパーツの衝突、P はパーツの省略です。 オートマトンの内部状態は、オートマトンがグループのどの部分をすでに形成したかというオートマトンの記憶を反映しています。 グループが形成されると、マシンは、不適切な部品が到着したときに状態を変更することなく、これらの状態を周期的に移動します。 遷移出力図を図に示します。 7.

2. アルファベットのコーディング。

可能なエンコード オプションの 1 つを次の表に示します。

入出力ステータス

3. オートマトンの標準構造の構築。

開発したオートマトンの正準構造を図に示します。 8.

SFE 出力の変数への依存関係を最初に表形式 (表 8) で見つけて、それに基づいて式を構築します。

表8

これらの関数は、いつ定義されるかが決まっていないため、部分的に定義されていると呼ばれます。 これらの関数を数式で表すために、より単純な形式の数式が得られるように関数をさらに定義します。

4. オートマトンの出力関数とメモリ管理関数を数式で表現。

ブール関数を最小化する方法を使用して、基底の式を使用して関数の最も経済的な表現を構築します。

5. SFE とマシンの最終回路の実装 (図 9)。

有限マシンの定義と指定方法。 合成の問題。 基礎機械