私はメンバーシップアルゴリズムを研究しており、次のようなこの特定の問題に取り組んでいます:
任意の正規言語 L が与えられたときに、L = L* かどうかを判断するアルゴリズムを示してください。
したがって、私の最初の考えは、L の Kleene スターである L* があり、L = L* かどうかを判断するために、L は正則であるため、L* は定義により、正規言語のファミリは、スター クロージャの下で閉じられています。したがって、L は常に L* と等しくなりますか?
それには間違いなくもっと多くのことがあると感じています。おそらく私が見逃しているものがあるでしょう。どんな助けでも大歓迎です。再度、感謝します。
L は正則なので、L* は定義上、正則言語のファミリーがスター クロージャの下で閉じていることを示していることがわかります。したがって、L は常に L* と等しくなりますか?
いいえRegular(L) --> Regular(L*)、しかし、それはそれを意味するものではありませんL == L*。2 つの言語がどちらも正規語だからといって、それらが同じ正規語であるとは限りません。たとえば、a*とb*はどちらも通常の言語ですが、同じ言語にはなりません。
の例はL != L*言語L = a*b*であり、したがってL* = (a*b*)*. 文字列ababは の一部ですL*が、一部ではありませんL。
アルゴリズムに関する限り、正規言語の概念は DFA によって解析できる概念であることを思い出してください。任意の特定の DFA について、その DFA の最適な縮小が 1 つあります。
あなたが述べた含意は間違っています。クリーネ星の下での閉鎖性は、L が正則である場合、L* が再び正則であることのみを意味します。L = L* かどうかを確認する 1 つの可能性は、両方の最小オートマトンを計算してから、等価性を確認することです。