Java'da bir NFA benzetimini yapmak için bir ödev verdim. Şimdi bir NFA simüle etmek zorunda aşağıdaki normal ifade Ben çok fazla e-semboller varJava'da NFA simülasyonu
ab*((b|d)|c*)
olduğunu. Sadece aşağıdaki aşağıdaki resmin doğru olup olmadığını merak ediyordum.
Kişisel NFA grafiği doğrudur. Bu regex ab*((b|d)|c*) eşleşecek ve başka bir şey. Bununla birlikte, çok daha basit olabilir, ör. Böyle:
Bunun tamamen doğru olduğunu sanmıyorum, dallanma kısmı '((b | d) | c *)' iki daldır, üç değil, ya (b | d) ya da c *, yani 'b' Düğüm, daha sonra “b” ya da “d” ye dallanıp tamamen ayrı bir yol olarak temsil etmeyi daha doğru olmaz mıydı? –
Yukarıdakilerin Thompson yapımı kullanmadığından eminim. Daha kısa ama öğretim görevlisi tarafından nasıl yapılacağına dair bir stil verildi. – unleashed
@unleashed, Thompson'ın bir NFA, bir NFA türü değil, bir algoritma (bir prosedür) olduğunu söyleyebilirim. NFA'mı Thompson ile oluşturulmuş bir şey olarak görebilir ve daha sonra optimize edebilirsiniz. (BTW: Soru, NFA'nızın normal ifadenize eşdeğerdir. Thomspon hakkında bir şey yok :-)) –
Düğümler 10, 11, 12 ve 13 muhtemelen sadece iki düğümler içine yoğunlaşmış olabilir? –
Ben başlangıçta ama yine de öğretim görevlisi tekrar tekrar için kullanarak ve NFA oluşturmak için Thompson inşaat kullanarak stil istiyor. Ben sadece 2 ila 3 e geçiş, 3 ila 4 e geçiş ve 4 ila 5 veya 4 ila 7 e geçiş olduğundan şüpheliyim. – unleashed
Eh, 2-3 azaltılabilir, 'b *' sonuçta hiçbir 'b' ile 1-2 arasında bir' e' geçişiniz olur. Bunun dışında kalanların uygun olduğunu düşünüyorum. Sonuçta sonuç aynı, sadece bir tane daha az düğüm. –