rのrとDFAが定義されたときのr *のDFAの発見

Question

rのrとDFAが定義されたときのr *のDFAを見つける方法をこの例でお伝えしたいと思います。どのように考えている？私は教科書を読みましたが、私ははっきり理解できません。ありがとうございました。

Answer 1

r *は、rからの0,1,2,3,4、...文字列の連結であるすべての文字列を含む言語です。したがって、r *の明白なFAは、r 0,1,2,3,4、...時間のDFAを実行し、これらのいずれかの実行後に受け入れることができるものです。任意の受け入れ状態から開始状態へのラムダ/空の遷移は、1回以上の実行を達成する。結果として生じるオートマトンはもはや決定論的ではない。標準的な方法を使用してそれを決定することができます。この構造は、空の文字列をオートマトンの言語に追加しません。すでにrに入っている場合、これは必要ではありません。それ以外の場合は、新しい開始状態など、r *のオートマトンに空の文字列を受け入れる方法を追加する必要があります。

空のトランジションを削除した経験があるため、簡単な場合にはより直接的にDFAを構築することもできます。