Jaki jest dobry algorytm do generowania losowych DFA?

9

Generuję losowe DFA, aby przetestować na nich algorytm redukcji DFA.

Algorytm, którego teraz używam, jest następujący: dla każdego stanu , dla każdego symbolu w alfabecie dodaj do jakiegoś losowego stanu. Każde państwo ma takie samo prawdopodobieństwo, że stanie się stanem końcowym.qdoδ(q,do)

Czy to dobra metoda generowania obiektywnych DFA? Ponadto ten algorytm nie generuje przycinanego DFA (DFA bez przestarzałych stanów), więc zastanawiam się, czy istnieje lepszy sposób generowania losowych DFA, który może w jakiś sposób zapewnić, że jest przycięty?

algorithms finite-automata randomness pseudo-random-generators random-graphs Duncan
źródło
2
Nie ma naturalnego rozkładu losowych DFA, więc to zależy od Ciebie. Co chcesz osiągnąć?
Yuval Filmus
Generuję losowe DFA, aby przetestować na nich algorytm redukcji DFA.
Duncan
Być może chcesz zacząć od małego zestawu minimalnych DFA i wysadzić je w powietrze? W ten sposób wiesz, że minimalizacja faktycznie prowadzi do właściwego wyniku.
adrianN
zastanawiasz się, czy testujesz nieoptymalny algorytm redukcji, czy znajduje unikalny minimalny optymalny DFA?
vzn
2
Jeśli generujesz struktury danych do testowania, obiektywne nie jest ważne. Ważne jest, aby mieć szansę na wywołanie interesujących zachowań. Aby przyjąć analogię, podczas testowania algorytmu geometrycznego musisz upewnić się, że niektóre z twoich testów będą miały wyrównane trzy punkty i inne rzeczy, które nigdy nie wystąpiłyby w rozkładzie losowym.
Gilles „SO- przestań być zły”

Odpowiedzi:

6

Sprawdź [1] i dyskusję w rozdziale 4, Generowanie losowych automatów. Papierowe testy porównują różne algorytmy minimalizacji DFA. Zastosowano jednolity generator losowy, który wytwarza kanoniczne reprezentacje ciągów kompletnych DFA z stanów i symboli. Omawiają także inne metody.nk

[1] Almeida, M., Moreira, N., i Reis, R. (2007). Na wydajność algorytmów minimalizacji automatów. Logika i teoria algorytmów, 3.

Juho
źródło
Co oznaczają „kanoniczne reprezentacje ciągów”?
Duncan
@drowse Porządek kanoniczny definiuje się nad zbiorem stanów, przechodząc przez automat w pierwszej kolejności, wybierając w każdym węźle wychodzące za pomocą (całkowitej) kolejności . Sprawdź odniesienia w artykule. Σ
Juho
4

Powinieneś spojrzeć na stronę domową Cyrila Nicauda . W szczególności następujące pytania dotyczą twojego pytania:

F. Bassino, J. David i C. Nicaud, Wyliczenie i losowe generowanie prawdopodobnie niekompletnych automatów deterministycznych, Pure Mathematics and Applications 19 (2-3) (2009) 1-16.

F. Bassino i C. Nicaud. Wyliczanie i losowe generowanie dostępnych automatów. Teoria Komp. Sc. . 381 (2007) 86–104.

J.-E. Kołek
źródło
3

Istnieją algorytmy losowego generowania DFA aż do permutacji http://paranthoen.thomas.free.fr/PAPERS/RandDFAToAppearInTCS.ps.gz .

Jednak w powyższym artykule wspomniano również, że prawie wszystkie DFA są już minimalne. Nie minimalne DFA są jak liczby pierwsze ... jest ich tylko kilka. A jeśli użyjesz tego algorytmu do przetestowania algorytmu minimalizacji, będzie to tak, jakbyś testował algorytm na liczbie pierwszej za pomocą prostego generatora liczb losowych. Aby mieć więcej niż minimalne DFA, możesz zmienić algorytm, dodając stan ujścia i przekierowując ważny procent przejść do tego stanu ujścia.

Ale z mojego punktu widzenia, jeśli chcesz przetestować szybkość swojej implementacji, sprawdź to, do czego chcesz go użyć: z losowymi zestawami słów lub losowymi REGEX, utwórz NFA lub DFA, a następnie zminimalizuj wynikowy DFA .

Tomasz
źródło
2

jedną naturalną strategią jest traktowanie DFA jako wykresu, a następnie istnieje wiele „naturalnych” i dobrze zbadanych losowych rozkładów grafów, najprostszym jest prawdopodobnie Erdos-Renyi . w takim przypadku traktujesz wszystkie stany DFA jako węzły wykresu i wybiera się stały procent wszystkich możliwych krawędzi (przejść DFA). bardziej wyrafinowane rozkłady, które są badane znacznie w najnowszej erze, to małe wykresy świata . w przypadku strategii wymienionej w pytaniu najwyraźniej wybierasz przypadek szczególnyp=1/n gdzie nto liczba węzłów na wykresie. jednak twoja strategia, ani Erdos-Renyi, nie gwarantuje, że wszystkie stany w DFA są połączone [naturalne ograniczenie, które należy dodać].

vzn
źródło
1
Do Twojej wiadomości: cs.stackexchange.com/review/suggested-edits/6609
Gilles 'SO- przestań być zły'
Jeśli chodzi o edycję, innym sposobem na zobaczenie DFA jest zestaw trójek definiujących krawędzie (v1,b,v2)) gdzie v1 jest wierzchołkiem 1, v2) wierzchołek 2 i bjest symbolem przejścia, a dowolny ich podzbiór można wybrać w celu ustalenia DFA.
vzn