I have seen descriptions for an algorithm that can take a regular deterministic finite automata and create a non-deterministic finite automata that is guaranteed to generate the reverse of string accepted by the DFA. Does anyone know of a "formal" proof that shows this is true in all cases? Guessing induction would be used to prove?(adsbygoogle = window.adsbygoogle || []).push({});

The algorithm goes something like this:

Take original DFA, and change the initial state to the final state

Reverse all accepting states in DFA to non-accepting states

Set original starting state to accepting state and reverse all transitions

Any thoughts would be greatly appreciated!

**Physics Forums - The Fusion of Science and Community**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Reversing a regular deterministic finite automata

Loading...

Similar Threads - Reversing regular deterministic | Date |
---|---|

B Reverse Mathematics Book | Feb 20, 2018 |

A Question about axiom of regularity | Sep 13, 2016 |

'Reverse' derive correct dataset when given mean + std dev | Jun 17, 2015 |

When are Markov processes non-reversible? | Feb 23, 2014 |

Skewness, logarithm and reversing in statistics | Apr 28, 2013 |

**Physics Forums - The Fusion of Science and Community**