(Yani geri referansları gibi düzensiz özellikleri kullanmak yok) aslında normal olan normal ifadeler için aşağıdakileri yapabilirsiniz:

1. Sonlu otomata içine regexen Transform (bunun için algoritma bulunabilir örneğin here (bölüm 9)).
2. Eğer devlet x1y2 içinde iseniz, (Siz iki otomata devletlerin kartezyen çarpım her devlet için bir devlet var. Daha sonra orijinal otomata geçişi kurallarına göre durumları arasında geçiş. Örneğin otomata kavşak inşa bir giriş olsun, ilk otomat giriş x için bir geçiş x1> x4 vardır ve ikinci otomat y2-> Y3 vardır, sen) devlet x4y3 içine geçiş.
3. Başlangıç ​​durumundan bir yol yeni bir otomat son durumuna orada olup olmadığını kontrol edin. Varsa, iki regexen aksi onlar değil, kesişir.

Bir düzenli ifade dizeleri bir potansiyel olarak sonsuz dizi tanıyan bir sonlu durum makinesi belirtir. Dizeleri kümesi sonsuz olabilir ama devletlerin sayısı sonlu olması gerekir, bu yüzden devletleri tek tek inceleyebilirsiniz.

İkinci örnek alarak: ilk ifadede, devlete 1 eyalete 0 almak, dize bir rakam ile başlamalıdır. İkinci ifadede, devlete 1 eyalete 0 almak, dize bir harf ile başlamalıdır. Yani İKİ ifadelerde devlete 1 0 durumunda sizi alacak hiçbir dize olduğunu biliyorum. Sen cevabım var.

İlk örnek alarak: Sen dize bir rakam ile başlıyorsa eğer düzenli ifade ile ya devlete 1 eyalete 0 alabilirsiniz biliyorum. Şimdi her biri için 0 durumu ortadan kaldırabilir ve sadece iki (şimdi bir devlet daha küçük) sonlu durum makinelerinin her biri için soruya cevap.

Bu bildiğiniz gibi bir Turing makinası veya eşdeğeri için genel durumda çözülemez bilinen "halting sorunu", gibi bir çok görünüyor. Ama aslında halting sorunun devletlerin sonlu vardır çünkü, sonlu-durum makinesi için çözülebilir IS.

Ben olmayan bir deterministik FSM ile bu çözebilir inanıyorum. Lütfen regex her devletten sonraki tek geçiş olsaydı, deterministik bir FSM çözebilir. Ama düzenli ifade karakter devlete 4 gitmek bir harf ise caracter başka, devlet 3 gitmek bir rakam ise, örneğin sonra, devlet 2 ise anlamına gelir.

Yani burada ben yapardım:

1. Sonraki bir devlet sadece bir geçiş var FSM yılların alt kümesi için bunu çözmek. Örneğin "Bob" ve "bob" ve sadece "Bob" ve "Bob" eşleşen ikinci bir regex hem eşleşen bir regex için.

2. Bir sonlu durum makinesinde çözümü uygulamak eğer bakın. Ben bunun mümkün olması gerektiğini düşünüyorum. Bir devlet için giriş bir FSM için bir geçiş ve ikinci biri için bir geçişi temsil eden bir çift. Örneğin: State 0: (R1, R2) (("B" ya da "B"), "b") ise, o zaman durum 1 State 1:. (R1, r2) (("O") ise, ( "o")) sonra devlet 2. vs

3. Şimdi örneğin devletin iki geri devlet iki veya daha önceki bir duruma gider daha genel durum, için; örneğin, regex 1 sadece "tanışma" tanır ama regex 2 E yıllardan sınırsız sayıda "meeeet" tanır. Siz "t" tanıma "t" ve regex 2 tanıma 1 regex için bunları azaltmak gerekir. Ben bu deterministik olmayan bir FSM tarafından çözülebilir olabilir düşünüyorum.

O zaten benim sezgi bulunuyor.

Benim sezgi her adımda bir devlet tarafından her regex kısaltmak gerekir söyler, sırf bu NP-tam olduğunu sanmıyorum.

Theory.

Java library.

Kullanımı:

/**
 * @return true if the two regexes will never both match a given string
 */
public boolean isRegexOrthogonal( String regex1, String regex2 ) {
   Automaton automaton1 = new RegExp(regex1).toAutomaton();
   Automaton automaton2 = new RegExp(regex2).toAutomaton();
   return automaton1.intersection(automaton2).isEmpty();
}

Mümkündür. Semantik web teknolojileri öğrenirken ben Pelet OWL Reasoner ile bir kez karşılaştı.

Here is an example, düzenli ifadeler, bir ağaç yapısı içine ayrıştırılamaz nasıl gösterir. Daha sonra (teoride) ağaçları için iki düzenli ifadeler ayrıştırmak ve bir ağaç diğer ağacın, yani bir alt kümesi olup olmadığını görebiliyordu. bir ağaç başka ağacın düğümleri içinde bulunabilir eğer.

Bu bulunursa, daha sonra diğer normal ifade ilk düzenli ifade maç olacak ne bir alt kümesini (değil sadece, aynı zamanda) maç olacak.

Bu bir çözüm değil çok, ama belki size yardımcı olacak.

Sizin soru dize eşleme sorunmuş gibi, ama aslında iki ayrı devlet makineler, bazı girdi verilen bir 'kabul' durumunu ulaşabileceğini kanıtladı edilebilir olsun veya olmasın, çok ilginç bir sorun ifade eder.

Bu benim (kuşkusuz eğitimsiz) göz için oldukça teorik hesaplanabilme sorun gibi görünüyor. Başkasının herhangi bir düşünce var mı? NP-tam kokuyor ...