A generalized transition graph (GTG) is a transition graph whose edges are labeled with regular expressions or string of input alphabets rest part of the graph is same as the usual transition graph.
The label of any walk from initial state to a final state is the concatenation of several regular expressions, and hence itself a regular expression. The strings denoted by such regular expression are a subset of the language accepted by the generalized transition graph, with the full language being the union of all such generated subsets.
Formal definition of generalized transition graph:
A generalized transition graph is defined by a 5-tuple, are as follows;
- Q : A finite set of states.
- Σ : A finite set of input symbols.
- S : A non-empty set set of start states, S ⊆
- F : A set of final or accepting states F ⊆
- A finite set, δ of transitions, (directed edge labels) (u, s, v), where u, v ∈ Q and s is a regular expression over Σ.
Also check: Bellman ford algorithm in data structure
Informally a generalized transition graph is a collection of three things are as follows;
- GTG consists finite number of states, at least one of which is start state and some (maybe none) final states.
- GTG consist finite set of input letters (Σ) from which input strings are formed.
- Directed edges in GTG connecting some pair of states labeled with regular expression.
It may be noted that in GTG, the labels of transition edges are corresponding regular expressions.
Example:
This GTG accepts all strings without a double b. Note that the word containing the single letter b can take the free ride along the ∧-edge from start to middle, and then have letter b read to reach to the final state. The first edge should be labeled (ba + a) as in the figure above, not (ab + a).
Also Check: History of python
Note: There is no difference between the Kleene star (*) closure for regular expressions and a loop in transition graphs, as illustrated in the following figure.
Consider the even-even language, defined over Σ = {a, b}. As discussed earlier that even-even language can be expressed by a regular expression (aa+bb+(ab+ba)(aa+bb)*(ab+ba))* The language even-even may be accepted by the following GTG.
Also Check: Principles of programming languages
