正規表現の同等性

Question

があるので、すぐの場合は任意の正規表現と同等の?ような複雑な問題があDFA簡素化機構は何かな？

Answer 1

あなたが表現のための最小限のDFA をrel="noreferrer"> href="http://www.google.de/search?hl=en&q=minimal+dfa"

Answer 2

平等のテスタビリティは、正規表現の古典的特性の一つです。 （N.B.あなたが本当にPerlの正規表現または他のいくつかの技術的にの非正規のsuperlanguageの話をしている場合、これが成立しない。）

、その後、一般の有限オートマトンAとBにあなたのREを回しAの受理状態がBの開始状態にヌル遷移を持っているように、新たなオートマトンA-Bを構築し、Bの受理状態が反転していること。これは、あなたB.によって受け入れられたすべてのものを除き、Aで受け入れ、すべてのこれらの文字列を受け入れオートマトンを与えます。

B-Aについても同じ操作を行い、純粋なのFAの両方を削減します。 FAは、開始状態からアクセス可能一切受理状態を持っていない場合、それは空の言語を受け付けます。あなたはA-BとB-Aの両方が空であることを示すことができるならば、あなたはそのA = Bを示してきました。

Editふむ、私は誰もが巨大な誤りに気づいていないと信じてすることはできません - 意図的なものを、コース:-Pの

オートマトンA-B説明したように、その前半Aによって受け入れられ、その後半B.ビルディングによって受け入れられていない所望の A-B若干トリッキープロセスであるこれらの文字列を受け入れます。私は私の頭の上から、それを考えることはできませんが、私はそれが明確に定義されたことを知っているか（そしておそらくAとBにおける非受容状態での状態を受け入れるの製品を表現するために状態を作成する必要が）。

Answer 3

これは本当にあなたが正規表現で何を意味するかに依存します。他のポスターが指摘したように、彼らの最小限のDFAに両方の式を低減することが動作しますが、それが唯一の純粋な正規表現のために働く必要があります。

現実世界の正規表現のlibs（特に後方参照）で使用した構築物の

いくつかのDFAアルゴリズムは彼らのために動作しませんので、それらを定期的でない言語を表現する力を与えます。たとえば、正規表現：([a-z]*) \1は、スペースで区切って（a aとb bしかしb aもa bない）同じ単語の二重の出現にマッチします。これは、すべての有限オートマトンによって認識されないことができます。

Answer 4

これら二つのPerlmonksスレッドについて具体的には、読みblokheadの対応):

• 比較satisfiabilityのregexps
• 試験regex同等性