Constructing an automaton graph representation for stack polygons and bar-graph polygons

• Main Author: Lapus, Raymond R.
• Format: text
• Published: Animo Repository 2009
• Subjects: Polygons; Mathematics
• Online Access: https://animorepository.dlsu.edu.ph/faculty_research/7818
• Institution: De La Salle University

An automaton A is a five-tuple (Σ, A, τ, ι, F) such that Σ is the collection of states; A is the alphabet set; τ: Σ x A → Σ is the transition function defined by τ ( s, a) s', for some s' ∈ Σ; ι ∈ Σ is the initial state; and a non-empty set F ⊆ Σ is the collection of final states. A is pictorially identified with a pictorial representation of a "labeled" directed graph with vertices v ∈ Σ and with an edge (s, t) labeled by a ∈ A if and only if τ(s, a) = t for s, t ∈ Σ and a ∈ A. A word v = v1v2 • • • vk over the alphabet A is a sequence of letters Vi ∈ A such that τ(ι, v1) = s1 only if sk ∈ F. The collection of all recognized words by A is the language L (A) of A. Let G (m, n) = [1..m]x[1..m] ⊆ Z2 be a grid. A self-avoiding polygon over a G is a sequence of points W = nk=0 such that |wk-1 – wk| = 1 for each k (l ≤ k ≤ n) and w0 n. = Wn. The line connecting wk-l and Wk is referred as the step sk in W for k = 1,2,…,n. This paper only considers two subclasses of self-avoiding polygon: the bar-graph polygon and the stack polygons. A "weak" automaton is constructed for each of these class of self-avoiding polygons. Each step from the walk W that formed these polygons are taken from the alphabet A= {d, l, r, u} representing the usual four-directional steps (up, down, right and left) from an arbitrary point in Z2. Furthermore, restrictions are imposed on the language of the automat representation for the class of stack polygon so that the words recognized by this automaton represents a walk forming an arbitrary stack polygon. The same procedure is done for the class of bar-graph polygons.