次のFSTを検討してください。
T1
0 1 a : b
0 2 b : b
2 3 b : b
0 0 a : a
1 3 b : a
T2
0 1 b : a
1 2 b : a
1 1 a : d
1 2 a : c
これらの2つのFST（つまり、T1またはT2）で合成操作を実行するにはどうすればよいですか？いくつかのアルゴリズムを見ましたが、あまり理解できませんでした。誰かがそれを簡単な方法で説明できれば、それは大きな助けになるでしょう。
これは宿題ではないことに注意してください。例は、解決策が示されている講義のスライドから取られていますが、私はそれを取得する方法を理解できませんでした。
入力形式を指定しなかったので、0 が初期状態であると想定しています。最初の列ではなく 2 番目の列に表示される整数は状態を受け入れ (T1 の場合は 3、T2 の場合は 2)、各行は前の状態、次の状態、入力文字、出力文字を与える遷移関係の要素。
FST に対するすべての操作は、新しい FST を生成する必要があるため、状態、入力アルファベット、出力アルファベット、初期状態、最終状態、および遷移関係が必要です (以下の FST A、B、および W の仕様はこの順序で与えられます)。 ）。FST が次のとおりであるとします。
A = (Q, Σ, Γ, Q 0 , Q F , α) B = (P, Γ, Δ, P 0 , P F , β)
そして、私たちは見つけたい
W = (R, Σ, Δ, R 0 , R F , ω) = A ∘ B
W のアルファベットを決定する必要がないことに注意してください。構成の定義はそれを行います。
A の出力テープが B の入力テープとして供給され、A と B を直列に実行していると想像してください。結合された FST の状態は、単純に A と B の結合された状態です。つまり、合成の状態は、個々の FST の状態の外積になります。
R = Q × P
あなたの例では、 W の状態は整数のペアになります。
R = {(0,0), (0,1), ... (3, 2)}
これらの番号を付け直して取得することもできますが (たとえば):
R = {00、01、02、10、11、12、20、21、22、30、31、32}
同様に、構成された FST の初期状態と受け入れ状態は、コンポーネント FST のクロス積です。特に、A と B の両方が文字列を受け入れる場合、R は文字列を受け入れます。
R 0 = Q 0 × P 0 R F = Q F × P F
例では、R 0 = {00} および R F = {32} です。
あとは、遷移関係 ω を決定するだけです。このために、A の各遷移ルールと、適用される可能性のある B のすべての遷移ルールを組み合わせます。つまり、A の各遷移規則を、入力文字として「γ」を持つ B のすべての規則と組み合わせます。(qi, σ) → (qj, γ)
ω = { ((q i , ph ), σ) → ((q j , p k ), δ) : (q i , σ) → (q j , γ) ∈ α,
(p h , γ) → (p k , δ) ∈ β}
この例では、これは、(たとえば) 0 1 a : bT1 と0 1 b : aT21 2 b : aを組み合わせて次のようになることを意味します。
00 11 a : a 01 12 a:a
0 2 b : b同様に、 T1 と0 1 b : aT2 1 2 b : a、0 0 a : aT1 と1 1 a : dT2 1 2 a : c&cを組み合わせます。
到達不能な状態 (「次の」状態として表示されない状態) と、決して発生しない遷移 (到達不能な状態からのもの) がある場合があることに注意してください。最適化のステップとして、これらの状態と遷移を削除できます。ただし、それらをそのままにしても、構造の正確性には影響しません。それは単なる最適化です。
グラフィカルな説明に慣れている場合は、次の一連のスライドで、実際の合成アルゴリズムの段階的なグラフィカルな例を提供し、コンポーネント トランスデューサのイプシロン トランジションの説明も含まれています。イプシロン遷移は合成プロセスを複雑にし、使用されているセミリングによっては、この場合、outis answer で説明されているアルゴリズムが正しい結果を生成しない可能性があります。
グラフィックの例については、スライド 10 ～ 35 を参照してください。