Generalized transition graph (GTG) definition with Example

19030

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;

  1. GTG consists finite number of states, at least one of which is start state and some (maybe none) final states.
  2. GTG consist finite set of input letters (Σ) from which input strings are formed.
  3. 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:

GTG Example
Figure 1 : Generalized Transition Graph (GTG) 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.

GTG Example
Figure 2 : Generalized Transition Graph (GTG) Example

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

Previous articleFinite automata with output | Transducer formal definition
Next articleParallel algorithm design Approach | PCAM
Er Parag Verma
Hello I am Er Parag Verma. I am tech blogger, Professor and Entrepreneur. I am on the mission to change the pattern of learning to make it easy, valuable and advance.

LEAVE A REPLY

Please enter your comment!
Please enter your name here

This site uses Akismet to reduce spam. Learn how your comment data is processed.