定例言語の閉鎖

Question

a） $ l $ を正規言語にする。理論体によると、言語を受け入れるDFAがあります。

$ l ^ r $ を受け入れるNFAにDFAを変更する方法を説明します。ここで、Rは逆です。

正式または証明または正確さを構築する方法を書く必要はありません。

b）trueまたはfalse： $ l $ の場合 $ l ^ r $ 通常

ではありません

私の解決策：

a）まず第一に受容状態を逆にしたいので、開始状態と拒否状態が受け入れられるようになるので、エッジの方向を反対側に変更します。 しかし、それがNFAにそれを変えることになると、少しずっと立ち往生しています。

b）それが正規であるともちろん $ l ^ r $ も同様に定期的になるならば、私はそれが逆になるので真実だと思います。

はAとBのための道ですか？

Answer 1

a）

まず、受付状態を逆にしたいと思うので、拒否状態が受け入れられるようになるため、エッジの方向を反対側に変更します。

あなたはほとんどそこにいます。元のDFAに複数の受け入れ状態がある場合はどうなりますか？それがあなたがそれらを変換するためにNFA機能を必要とする場所です。

ここにあなたがあなたの答えをチェックしたい場合のスポイラーです： DFAの設計とコンピュータ透過症に関する逆の

b）

あなたの答えはそれをもう少し慎重にフレーズしたいと思うかもしれませんが「 $ l $ が正規でない場合は、「 $ l ^ r $ が正規ではありません " 。そのため、 $ l $ を正規ではありません。 $ l ^ r $ が定期的にあったので、 $（l ^ r）^ r= l $ でした。これは矛盾です。したがって、 $ l ^ r $ は正規ではありません。