Pytania otagowane jako minimization

2
Czy automaty XOR (NXA) dla języków skończonych korzystają z cykli?
Niedeterministyczne automaty Xor (NXA) są składniowo NFA, ale mówi się, że słowo jest akceptowane przez NXA, jeśli ma nieparzystą liczbę ścieżek akceptacji (zamiast co najmniej jednej ścieżki akceptacji w przypadku NFA). Łatwo zauważyć, że dla skończonego języka regularnego LLL istnieje minimalny NFA, który nie zawiera żadnych cykli (jeśli cykl był …
1
Minimalizowanie resztkowych automatów skończonych
Automaty szczątkowego stanu skończonego (RFSA, zdefiniowane w [DLT02]) to NFA, które mają kilka fajnych cech wspólnych z DFA. W szczególności zawsze istnieje kanoniczny minimalny rozmiar RFSA dla każdego zwykłego języka, a język rozpoznawany przez każdy stan w RFSA jest resztkowy, podobnie jak w DFA. Jednakże, podczas gdy minimalne stany DFA …
2
Uogólnienie algorytmu minimalizacji DFA Brzozowskiego do automatów skończonych z różnymi klasami stanów akceptujących?
Algorytm Brzozowskiego do przekształcania DFA w równoważny DFA stanu minimalnego jest niezwykle prosty: jeśli oznacza NFA utworzony przez odwrócenie wszystkich krawędzi w DFA , czyniąc stary stan początkowy stanem akceptującym i czyniąc starym akceptowaniem stwierdza początek stanów i jeżeli oznacza wynik zastosowania konstrukcji podzbioru do NFA , a następnie jest …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.