Ölü veya gereksiz durumlara sahip bir DFA oluşturan düzenli ifade

Question

Sözcüğümde bir DFA minimizatörü uygulamak istiyorum; ancak, DFA'nın daha düşük bir DFA'sı gibi görünmüyor. ifadesi.

DFA'yı bir postfix düzenli ifadesinden thomson yapısı kullanılarak oluşturulan bir NFA'dan yapıyorum. Ejder kitabında tam olarak anlatılan şey tam olarak bu. Lexer'ı birkaç NFA'nın yapmak için başlangıç ​​durumundan epsilon geçişleri kullanılarak birleştirilir. DFA algoritmasının uygulandığı bu birleştirilmiş NFA'da var. Öyleyse, ölü durumun ortadan kaldırılması ve devletin en aza indirilmesi için güzel bir test yatağı yapacak bir DFA yaratacak herhangi bir "bilinen" düzenli ifade var mı?

Elbette garip bir DFA'yı kesebilir ve üzerinde algoritmalar uygulayabilirim, ancak bu gerçekten uygun bir test durumu olmaz mıydı? Öyleyse, DFA'ları yapılandıracağım yöntemin ölü durumlara eğilimli olmaması durumunda, o zaman bu bilgi, değerli olarak uygulanabilirdi, o zamandan beri, devlet eleme özelliğinin tamamen uygulanmasını atlayabilirim.

Düzenleme: Eğer doğru cevap verebilmek için uygulama ayrıntılarını ihtiyaç durumda, kod, özellikle NFA.cs ve DFA.cs sınıflar github mevcuttur. Ayrıca kullanıyorum inşaat algoritması üzerinde blog posts bir dizi yazdım, eğer bu yardımcı olur.

Answer 1

Tamam, bunu tamamen dolambaçlı bir yolla buldum. Ayrıştırıcımdan oldukça iyi bir hata ayıklama çıktısı aldığımdan düzenli ifadeyi görselleştirmek için bir araç hazırladım. aracında Gösterildi (a+b+c+)+|abc

: http://regexvisualizer.apphb.com/?Regex=%28a%2Bb%2Bc%2B%29%2B%7Cabc&NfaSize=300&DfaSize=250#

Bu araç şu anda herhangi bir optimizasyon olmadan düzgün, Thompson yapımını gerçekleştiren Bu uygun bir şekilde standart Thompson yapı tekniklerini kullanarak size güzel aptal otomata verecek şekilde bir ifade göstermektedir. İfadenin tamamen gereksiz olduğu |abc bölümünü kaldırırsanız, ifade aynı kalmalıdır. Olmaz.