automata - オートマトンと形式言語

Question

正規言語 L の単語の反転も正規であることを示す

この質問にどのようにアプローチするかについて私は混乱しています。何時間も立ち往生しています。単語 x の場合、x^r を使用してその逆を示します。言語 L の場合、L^r を使用して {x^r (x は L のセット内)} を表します。L が正則なら L^r も正則であることを示す

score 1 · Accepted Answer

が規則的である場合L、それを生成するいくつかの規則的な文法が存在します。これは常に、左規則文法または右規則文法のいずれかとして表すことができます。それが左正則文法であると仮定しましょうG_l(右正則文法の証明も同様です)。

この文法には 2 つのタイプの生成があります。終了タイプ:

A -> a, where A is non-terminal and a is either a terminal or empty string (epsilon)

または連鎖タイプ：

B -> Ca, where B, C are non-terminals and a is a terminal

通常の言語にリバースを適用すると、基本的にプロダクションの末尾にも適用されます (先頭は単一の非終端記号であるため)。それは後に証明されることになる。G_rしたがって、プロダクションを使用して新しい grammar を取得します。

A -> a, where A is non-terminal and a is either a terminal or empty string (epsilon)
B -> aC, where B, C are non-terminals and a is a terminal

でもちょっと、それは正しい正則文法です! そのため、受け入れる言語も規則的です。

しなければならないことが 1 つあります。それは、テールの反転が実際に想定されていることを実行することを示すことです。非常に簡単に証明します。

\epsilon が含まれている場合L、に 'S -> \epsilon' というプロダクションがありG_lます。そのようなプロダクションには触れないので、にも存在しG_rます。
Lが含まれている場合a、単一の端末で構成される単語であり、上記と同様です
Lが含まれている場合aZ、 a は終端であり、Zはの単語から最初の終端を切り落として構築された言語の単語でLあり、L^r(連鎖生成が変更されたため) が含まれます(Z^r)a。Z は正規言語でもあります。これは、左生成の最初の「レベル」をから削除することで構築できるためG_l、通常の文法が残ります。

お役に立てば幸いです。関連する有限オートマトンのエッジを反転し、受け入れ状態と開始状態を少し変更することで、間違いなく簡単な方法もあります。

1 に答える 1