通常の言語クロージャが挿入されている

Question

アルファベットΣの正規言語Lがあるとします。途中に記号を挿入すると、言語L 'がまだ正規の言語であることをどのように表示するのですか？

たとえば、Lには2つの部分文字列uとv（w = uv）からなる文字列wが含まれています。正規言語L 'に文字列uxvが含まれていることを示します。

uとvは同じ長さである必要はなく、xも同じアルファベットΣであることに注意してください。

ありがとうございました！

Answer 1

Lは規則的なので、それを受け入れる有限オートマトンAが存在します。 Aの2つのコピー（A1とA2）を作成します.A2では開始状態を初期にしないでください。 A1のすべての状態pに対して、遷移p - x - > pをA2の対応する状態に加える。

あなたの例の表記法を使って、A1はuを読み取り、新しいトランジションはxを読み取り、A2はvを読み取ります。