4 Fix some Typos
source | link

There are algorithmalgorithms to randomly generate DFAs up to a permutation http://paranthoen.thomas.free.fr/PAPERS/RandDFAToAppearInTCS.ps.gz.

But, it is also mentionned in the above paper that almost all DFAs are already minimalsminimal. Non minimal DFAs are like prime numbers ... there are just few of them. And if you use this algorithm to test minimization algorithm it will be like if you were testing an algorithm on prime number with a simple random number generator. InIn order to have more non minimal DFAs, you may alter the algorithm by adding a sink state, and redirect aan important percentage of the transitions to this sink state.

But from my point of view, if you want to test the speediness of your implementation, check it against what you want to use it for: with random word sets or random REGEX, create a NFA or a DFA, and then minimize the resulting DFA.

There are algorithm to randomly generate DFAs up to a permutation http://paranthoen.thomas.free.fr/PAPERS/RandDFAToAppearInTCS.ps.gz.

But, it is also mentionned in the above paper that almost all DFAs are already minimals. Non minimal DFAs are like prime numbers ... there are just few of them. And if you use this algorithm it will be like if you were testing an algorithm on prime number with a simple random number generator. In order to have more non minimal DFAs, you may alter the algorithm by adding a sink state, and redirect a important percentage of the transitions to this sink state.

But from my point of view, if you want to test the speediness of your implementation, check it against what you want to use it for: with random word sets or random REGEX, create a NFA or a DFA, and then minimize the resulting DFA.

There are algorithms to randomly generate DFAs up to a permutation http://paranthoen.thomas.free.fr/PAPERS/RandDFAToAppearInTCS.ps.gz.

But, it is also mentionned in the above paper that almost all DFAs are already minimal. Non minimal DFAs are like prime numbers ... there are just few of them. And if you use this algorithm to test minimization algorithm it will be like if you were testing an algorithm on prime number with a simple random number generator. In order to have more non minimal DFAs, you may alter the algorithm by adding a sink state, and redirect an important percentage of the transitions to this sink state.

But from my point of view, if you want to test the speediness of your implementation, check it against what you want to use it for: with random word sets or random REGEX, create a NFA or a DFA, and then minimize the resulting DFA.

3 Improve Text
source | link

There are algorithm to randomly generate DFAs up to a permutation http://paranthoen.thomas.free.fr/PAPERS/RandDFAToAppearInTCS.ps.gz.

But, it is also mentionned in the above paper that almost all DFAs are already minimals. Non minimal DFAs are like prime numbers ... there are just few of them. And if you use this algorithm it will be like if you were testing an algorithm on prime number with a simple random number generator. In order to have more non minimal DFAs, you may alter the algorithm by adding a sink state, and redirect a important percentage of the transitions to this sink state.

But from my point of view, if you want to test the speediness of your implementation, check it against the usage that will be done ofwhat you want to use it for: with random word sets or random REGEX, create a NFA or a DFA, and then minimizedminimize the resulting DFA.

Thomas

There are algorithm to randomly generate DFAs up to a permutation http://paranthoen.thomas.free.fr/PAPERS/RandDFAToAppearInTCS.ps.gz.

But, it is also mentionned in the above paper that almost all DFAs are already minimals. Non minimal DFAs are like prime numbers ... there are just few of them. And if you use this algorithm it will be like if you were testing an algorithm on prime number with a simple random number generator. In order to have more non minimal DFAs, you may alter the algorithm by adding a sink state, and redirect a important percentage of the transitions to this sink state.

But from my point of view, if you want to test the speediness of your implementation, check it against the usage that will be done of it : with random word sets or random REGEX, create a NFA or a DFA, and then minimized the resulting DFA.

Thomas

There are algorithm to randomly generate DFAs up to a permutation http://paranthoen.thomas.free.fr/PAPERS/RandDFAToAppearInTCS.ps.gz.

But, it is also mentionned in the above paper that almost all DFAs are already minimals. Non minimal DFAs are like prime numbers ... there are just few of them. And if you use this algorithm it will be like if you were testing an algorithm on prime number with a simple random number generator. In order to have more non minimal DFAs, you may alter the algorithm by adding a sink state, and redirect a important percentage of the transitions to this sink state.

But from my point of view, if you want to test the speediness of your implementation, check it against what you want to use it for: with random word sets or random REGEX, create a NFA or a DFA, and then minimize the resulting DFA.

2 Improve Text
source | link

There are algorithm to randomly generate DFAs up to a permutation http://paranthoen.thomas.free.fr/PAPERS/RandDFAToAppearInTCS.ps.gz.

It is a paper published in 2004.

But, it is also mentionned in the above paper that almost all the DFAs are already minimals. Non minimal DFAs are like prime numbers ... there are just few of them. And if you use this algorithm it will be like if you were testing an algorithm on prime number with a simple random number generator. In order to have more non minimal DFAs, you may alter the algorithm by adding a sink state, and redirect a important percentage of the transitions to this sink state.

FromBut from my point of view, if you want to test the speediness of your implementation, check it against the usage that will be done of it : with random word sets or random REGEX, create a NFA or a DFA (Brzozowsky method), and then minimized the resulting DFA.

Thomas

There are algorithm to randomly generate DFAs up to a permutation http://paranthoen.thomas.free.fr/PAPERS/RandDFAToAppearInTCS.ps.gz.

It is a paper published in 2004.

But, almost all the DFAs are already minimals. Non minimal DFAs are like prime numbers ... there are just few of them.

From my point of view, if you want to test the speediness of your implementation, check it against the usage that will be done of it : with random word sets or random REGEX, create a NFA or a DFA (Brzozowsky method), and then minimized the resulting DFA.

There are algorithm to randomly generate DFAs up to a permutation http://paranthoen.thomas.free.fr/PAPERS/RandDFAToAppearInTCS.ps.gz.

But, it is also mentionned in the above paper that almost all DFAs are already minimals. Non minimal DFAs are like prime numbers ... there are just few of them. And if you use this algorithm it will be like if you were testing an algorithm on prime number with a simple random number generator. In order to have more non minimal DFAs, you may alter the algorithm by adding a sink state, and redirect a important percentage of the transitions to this sink state.

But from my point of view, if you want to test the speediness of your implementation, check it against the usage that will be done of it : with random word sets or random REGEX, create a NFA or a DFA, and then minimized the resulting DFA.

Thomas

1
source | link