Jak przekonwertować NFA na wyrażenie regularne

Wiedziałem, że konwersja wyrażenia regularnego na NFA, istnieje algorytm.Jak przekonwertować NFA na wyrażenie regularne

Ale zastanawiałem się, czy istnieje algorytm do przekonwertowania NFA na wyrażenie regularne. Jeśli jest, co to jest?

A jeśli tak nie jest, zastanawiam się również, czy wszystkie NFA mogą zamienić się na wyrażenie regularne. Czy istnieje NFA, które wyrażenie regularne, które nie może reprezentować?

Dziękujemy! : D

Źródło

2012-02-09 formatjam

regularne ekspresyjny może wyrażać * każdy o regularna języka, tak, że powinno istnieć przynajmniej jedno wyrażenie regularne dla każdej możliwej NFA. Jednak nie znam algorytmu przejścia z NFA do wyrażenia regularnego z mojej głowy. –

Również twój czas jest naprawdę niesamowity - mój przyjaciel zadał mi dokładnie to samo pytanie na dzisiejszej lekcji. Nie pamiętam też odpowiedzi :( –

Zobacz odpowiedzi na swoje pytanie: http://cs.stackexchange.com/questions/2016/how-to-convert-finite-automata-to-regular- wyrażenia – Masterfool

Tutaj jest algorytmem, gdzie każde przejście jest stopniowo zastąpiony regex, dopóki nie tylko początkowe i końcowe stanowią: https://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_08.pdf [PDF]

Źródło

2012-02-09 05:43:05 buzypi

to jest poprawne, ale to nie działa, jeśli masz dużo węzła, to jest dobre dla prostego i kilku węzłów, czy jest jakaś inna sugestia? –

Link jest martwy dla mnie. Znalazłem ten link: https://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_08.pdf –

Jak przekonwertować NFA na wyrażenie regularne

Odpowiedz

Powiązane problemy