Can a deterministic finite acceptor begin at the end of string and move toward the start?

54 views Asked by At

If so, how is this drawn as a graph? what would you label your start state? and would you draw the graph as moving from right to left as well?

1

There are 1 answers

0
J.-E. Pin On BEST ANSWER

Since your are dealing with deterministic finite automata, the answer is no.

The main problem is that you may have two transitions (p, a, r) and (q, a, r) leading to the same state r, but with p different from q. Then if you start in r and try to read the letter a backwards, should you end up in p or in q?