Chapter 6: Transition Graphs

Transition graph (TG): a generalization of a FA

FA:
(1) set of states, one of which is a start state, one or more of which are final states
(2) alphabet of input letters
(3) set of transitions, which can be represented as a function f(S,x)
             which, for some (state, letter) pairs (S, x) defines a new state Snew = f(S, x)
TG:
(1) can have more than 1 start state
(2) the same
(3) is different in the following way:

(a) instead of just an alphabet letter x, x can now be an arbitrary string w, including l
(b) f can be multiple-valued (not a function!): it can associated several states Snew with a given (S, w) pair. Example:



How does this machine work as a recognition device?

(1) a l -transition means that the machine can change state without consuming any input
(2) a multiple letter string means that the machine can remove that whole string from the input, and take the transition Question: Given the input string "abc", there are three possible transitions from state 1. Which one do you take?
Answer: you have to try all possible transitions at every stage. This represents a non-deterministic machine!

Question: What do we mean by acceptance, then?
Answer: If any legal sequence of states ends in a final state with the input string consumed, the string is accepted. Otherwise it is rejected.

(1) is "abc" accepted by the above machine?
(2) in how many ways?

Generalized Transition Graph
A transition graph where the edge labels are regular expressions (not just strings).

Hosted by www.Geocities.ws

1