Es sollte möglich sein, Automa.jl zu verwenden, um einen DFA zu erstellen und ihn zufällig zu durchlaufen. Automa verwendet eine einfachere Syntax als PCRE, daher sollte die Sprache, die Sie damit beschreiben können, eigentlich regelmäßig sein.
Ich habe schnell Folgendes zusammengeschmissen, hauptsächlich basierend auf dem Code in dot.jl
:
julia> function rand_re(machine::Automa.Machine)
out = IOBuffer()
node = machine.start
while true
if node.state ∈ machine.final_states
(rand() ≤ 1 / (length(node.edges) + 1)) && break
end
edge, node = rand(node.edges)
label = rand(collect(edge.labels))
print(out, Char(label))
end
return String(take!(out))
end
rand_re (generic function with 1 method)
julia> rand_re(Automa.compile(re"a[0-9][ab]+"))
"a6bbb"
julia> rand_re(Automa.compile(re"a[0-9][ab]+"))
"a9b"
julia> rand_re(Automa.compile(re"a[0-9][ab]+"))
"a3aa"
julia> rand_re(Automa.compile(re"a[0-9][ab]+"))
"a1a"
julia> rand_re(Automa.compile(re"a[0-9][ab]+"))
"a5ba"
Die Einschränkung besteht darin, dass Automa bytekodierte Sätze für Kantenbeschriftungen verwendet. Daher sollte beim Schreiben mehr Vorsicht geboten sein Char(label)
.
Da Endzustände immer noch ausgehende Kanten haben können, habe ich mich dafür entschieden, das Anhalten und jede Kante mit einheitlicher Wahrscheinlichkeit zu behandeln. Ich denke, dies wird wahrscheinlich dazu führen, dass potenziell unendliche Begriffe entweder sehr kurz oder sehr lang sind. google "Boltzmann Sampler", wie man das löst (nicht zu verwechseln mit Sampling aus einer Boltzmann-Distribution!), aber die Lösung ist eher mathematisch.
T
oder davonF
abhängt, ob die Teilmengen-Summe vorhanden ist. Wenn Ihr PCRE-Matching-Regex-Generator in Polynomzeit arbeitet, dann herzlichen Glückwunsch, Sie haben P = NP bewiesen.