言語Lが普通の場合、L 'は正規であることを示すには？

Question

Lを任意の正規言語とし、εΣとする。それをどのように表示するかL '= {uav | uv∈L}も規則的ですか？

ウィキペディアはプロービングする方法は通常の言語に戻すことだと述べていますが、私はこの場合どのように行うのか理解していません。誰かが助けることを願っています。

Answer 1

これを表示する方法はたくさんあります。私はDFAを構築する議論は特に視覚化が容易だと思います。

言語LのDFAを想像してみましょう。Mとしましょう。テーブルの上にダイアグラム形式で広がっていると想像してください。さて、Mのコピーを作ってテーブルの上にMの横に広げてみましょう。それをM'と呼んでください。今

からMから、M'の対応する状態q'からMの状態qから新しいトランジションを追加します。トランジションはシンボルaです。

ここで、開始状態が開始状態であるMで、受け入れ状態が受け入れ状態である集約マシンがM'であるとします。このマシンはLの文字列の受け入れを開始し、中間のどこかでaを受け入れ、それを中止したところからLの文字列を受け入れ続けます。これは私たちが行っていた言語であり、私たちはそれに対して完全に合理的なNFAを定義しました。 NFAが受け入れる言語はすべて正規言語であるため、私たちの言語は規則的です。