Microsoft Word - 7-V9N3(2024)-AITI#13599(239-255).docx Advances in Technology Innovation, vol. 9, no. 3, 2024, pp. 239-255 English language proofreader: Chih-Wen Teng A Novel Approach to Construct Finite Automata Using Grid and Product Automata Rupam Nag, Dibyendu Barman*, Abul Hasnat Department of Computer Science and Engineering, Government College of Engineering and Textile Technology, Berhampore, WB, India Received 19 April 2024; received in revised form 14 June 2024; accepted 17 June 2024 DOI: https://doi.org/10.46604/aiti.2024.13599 Abstract This research aims to utilize an organized grid-based strategy to make the development of complex Finite Automata easier. Product Automata are used to merge many automata into a single automaton to integrate various computing processes. Combining these methodologies provides novel methods of improving the scalability and efficiency of automata building, broadening the field of research for automata theory and its applications. The scalability of this developed automated system will benefit sectors such as automotive production and logistics. The results indicate considerable improvements in construction time, memory usage, scalability, and resilience compared to older approaches. The performance of the developed method, as measured by construction time, memory utilization, scalability, robustness, application range, and complexity, is 25% to 50% higher than that of traditional methodologies in the literature. Keywords: DFA, NFA, Grid, Product Automata 1. Introduction The theory of computation is divided into three areas: computational complexity theory, computability theory, and automata theory. These branches are the foundation for research into algorithms, mathematical aspects of computational models, and computability limitations. Automaton theory is concerned with abstract machines and their various forms, such as finite state automata, pushdown automata, and Turing machines. Each is defined by specific components such as states, input alphabets, transition functions, start states, and accepting states, which are necessary for understanding computation. Finite state automata are classified as deterministic finite automata (DFA) or non-deterministic finite automata (NFA), with representations such as transition diagrams or transition tables explaining their behavior. Automata theory extends beyond representation, with applications in formal language theory, compiler building, and software verification, all of which help solve complicated computational issues. Specifically, Grid Automata and Product Automata are effective approaches for generating Finite Automata: Grid Automata organize states in an organized grid-like pattern, simplifying construction and maintaining accuracy, whereas Product Automata combine several automata into composite structures using Cartesian products, allowing for efficient description of complicated systems. This investigation emphasizes the utility of Grid and Product Automata in the construction of Finite Automata, demonstrating their efficacy in addressing computing difficulties. Automata are the subject of studies in the literature. Some of them are addressed below. In 2024, Zhao et al. [1] designed a model that simulates the microstructural evolution of 7075 aluminum alloy under hot deformation based on cellular automata (CA). The material properties of the 7075 aluminum alloy were determined via isothermal compression testing, which resulted in the creation of models for dislocation density, recrystallized grain nucleation, * Corresponding author. E-mail address: dibyendu.barman@gmail.com 240 Advances in Technology Innovation, vol. 9, no. 3, 2024, pp. 239-255 and grain development. These results show that large strain, high temperature, and low strain rate promote dynamic recrystallization and grain refining. The CA model’s results indicate good accuracy and predictive capabilities, with an experimental error of less than 10%. The drawback of this approach is that, depending on the particular implementation, the model’s effectiveness may vary. Furthermore, even if CA models offer a more accurate depiction of geographical distribution, they could need more time and computing power. Again in 2024, Amir et al. [2] examine the Knuth-Morris-Pratt (KMP) automata and present a practical outcome that defies intuition. Also, Modanese and Worsch [3] in 2024, showed a fungal automaton with an update sequence horizontal- vertical (HV) can be configured to include any Boolean circuit in its initial state. For texts with uniformly random symbols, the naive technique is thought to perform as well as the KMP algorithm. In this study, the KMP algorithm’s practical efficiency is compared against a naive technique for generating a random text. It investigates the time under a variety of situations, including alphabet size, pattern length, and pattern distribution in the text. The main constraint of this approach is that data becomes less useful as input sizes grow. As a result, errors keep happening. In 2024, Pighizzini et al. [4], show using 1-limited automata, a constrained variant of one-tape Turing machines, the descriptional complexity of fundamental operations on regular languages is examined. The sizes of the generated devices are polynomial in the sizes of the simulated machines when deterministic 1-limited automata are used to simulate operations on DFA. Applying the operations to deterministic 1-limited automata presents a different scenario: the simulations stay polynomial for Boolean operations, but they become exponential in size for product, star, and reversal operations. The major drawback of this approach is that if the machines are two-way DFA, the costs of the product and star do not decrease. Maletti and Nasz [5] in 2024, showed that the central idea of the unweighted setting, the tree automaton with inequality and equality constraints, can be directly generalized to the weighted setting and can represent the image of any regular weighted tree language under any nonerasing and nondeleting tree homomorphism. Several closure properties and decision problems are also examined for the weighted tree languages produced by constraint-based weighted tree automata. The main limitation of this approach is that weighted tree automata cannot ensure that two subtrees in an approved tree, regardless of size, are always equal. In 2024, Laura et al. [6] proposed A model of CA that has been created to investigate the behavior of ceramic particles during sintering. Reducing the energy at the interface between the mass cells and the void cells is the single physical rule in this model that governs how the system evolves. Investigations were conducted into the significance of various computational factors, including particle size and computational temperature. Experiments with partial sintering of spherical silica particles were carried out, and it was confirmed that this model accurately replicates neck development. Furthermore, other experimental evidence of densification stages, such as the creation of the intermediate vermicular microstructure or the porosity-temperature dependence, were qualitatively replicated. The primary constraints of this approach are motion artifacts and the influence of grid resolution on motion. In 2023, Kishore et al. [7] proposed fundamental ideas and concepts of quantum-dot cellular automata (QCA), along with some potential benefits over traditional complementary metal-oxide-semiconductor (CMOS) technology. The performance of QCA-based adders is then compared to conventional CMOS designs, and it is demonstrated that QCA-based adders are faster and require less power than CMOS designs. Due to their small size and careful construction, the primary drawback of these QCAs is that they are more prone to errors. Again in 2023, Shahid et al. [8] presented the proactive approach in a peer group. Here a variety of group activities are used to make the course engaging and simple for the students to learn from with the support of their classmates. They were able to learn NFA as a result, and they also used simulation software to enhance the learning process. The main constraint of this approach is the restricted computational problem-solving capabilities of these machines, which are primarily limited to issues that can be described using regular languages. Advances in Technology Innovation, vol. 9, no. 3, 2024, pp. 239-255 241 In 2023, Jaiswal and Sasamal [9] proposed a method where in comparison to the horizontal, vertical, nanomagnetic QCA, and the current QCA-based 2:1 mux, the suggested compact design methodology results in approximately 71% to97% reduction in the total number of nanodots and approximately 22% to 99% reduction in area occupancy. Here it also creates an 8:1 mux to demonstrate the scalability of the suggested structure. Using the MuMax3 micromagnetic simulator, the design layouts and simulation results are confirmed. The main negative aspect of this approach is that, because of its small size and precise construction, it is more prone to faults. Havlena et al. [10] in 2023, proposed a method to lower the false-positive rate of the automata-based detection system and greatly enhance its performance. Furthermore, and importantly for real-world implementation, A technique is provided here that generates more details regarding discovered abnormalities, which is useful for real-world deployment. The method is illustrated using IEC 104 or multimedia messaging service (MMS) communication between multiple industrial control systems (ICS) systems. However, this suggested method’s success rate falls short of expectations. Again in 2022, Battyányi et al. [11] defined rough-set-like approximation spaces for formal languages over the defined alphabetic symbols using similarity relations. A methodology to be driven by circumstances when unsure of the precise characters that comprise a text that must be processed by a formal system is put forth in this work. It encompasses regular and context-free cases and specifies lower and higher approximations of languages. Descriptions of the approximate languages produced by context-free grammars or recognized by DFA are presented. This method’s primary flaw is the absence of characterizations for the approximate languages that NFA accepts. In 2022, Vogrin et al. [12] proposed a method that effectively traverses multiple transitions simultaneously by utilizing the symbolic representation. The process is assessed using industry-standard communication protocol models and biological system models. It is at least many times faster than the previous one, according to the results. When witness automata were initially presented, test sequence composition was made possible. Its primary flaw is that it occasionally yields results that are not entirely correct. Lastly, recent research has explored novel avenues within automata theory, particularly concerning graph operations and advanced compositions, including n-ary Cartesian composition and Cartesian product of automata [13-15]. This recent wave of research underscores the dynamic nature of the field, driving it forward into uncharted territories of exploration and innovation, contributing to the foundational understanding of automata theory and its diverse applications. The primary flaw in this approach is that the success rate is not high enough. The objective of this study is to use an organized grid-based method to make the construction of sophisticated Finite Automata simpler. Conversely, Product Automata is designed to combine several automata into a single automaton to integrate different computational processes. Combining these approaches offers novel methods to improve automata construction’s scalability and efficiency, expanding automata theory’s field of study and useful applications. The scalability of this built automated system will aid industries like automobile manufacturing and logistics in the future. Let us look at some more future automation options. This developed method will have a big impact on the robotics industry in the coming years. This technique can be used to create and build complex robots. This strategy will play an important role in the field of self-driving cars, which is a rising area of technology. 2. Notation and Basic Definitions (1) Deterministic finite automata (DFA): DFA consists of a 5-tuple M = (Q, Σ, δ, q0, F), where Q is a finite set of states, Σ is the finite or non-empty set of input symbols called the alphabet, δ is the transition function defined as Q × Σ → Q, q0 is the initial/start state (q0 ∈ Q), F represents the set of accepting or final states within the set of all states (F ⊆ Q). The notations for the states and transitions are shown in Fig. 1. 242 Advances in Technology Innovation, vol. 9, no. 3, 2024, pp. 239-255 (2) Non-deterministic finite automata (NFA): Similar to DFA, except that the transition function δ is defined as Q × Σ → 2Q. It is the Finite Automata that allows multiple transitions for a single input alphabet and, it doesn’t contain a dead or trap state. (3) Languages accepted by DFA: The language accepted by DFA M = (Q, Σ, δ, q0, F) is the set of strings Σ accepted by M, i.e., L(M) = {w ∈ Σ* / δ (q0, w) is in F}. (4) Input strings and symbols: Sequences of symbols from the input alphabet are used to drive the transitions of the automaton. Strings are typically represented as sequences of symbols from the input alphabet, e.g., w = a1a2...an, where each ai ∈ Σ. (5) Number of occurrences of a symbol ‘a’ in a string ‘w’: Denoted as n(a), represents the count of occurrences of the symbol ‘a’ in the string ‘w’. (6) Length of a string ‘w’: Denoted as |w|, it represents the number of symbols in the string ‘w’. (7) Empty string: Denoted as ε, it represents the string with zero symbols. (8) Language: Denoted as L, it represents a set of strings over some alphabet. (9) Cartesian Product: Given two sets A and B, the Cartesian product A × B is the set of all ordered pairs (a, b) where a is an element of A and b is an element of B. In mathematical notation: A × B = {(a, b) ∣ a ∈ A and b ∈ B}. The Cartesian product A × B contains all possible combinations of elements from sets A and B, preserving the order of elements. Fig. 1 Notations 3. Methodology Grid and product automata methods are essential to develop and analyze the various aspects of automata, leading to better computational models due to their ability to facilitate the faster design of complex automaton logistics. Specifically, the Grid Automata offers a systematic way to manage state transitions whereas Product automata are used to combine multiple concepts such as topology and partitioning of computing processes. These methods will be examined in detail in the following subsections. 3.1. Grid Automata The Grid Automata methodology is the organization of states into a structured grid pattern based on specific conditions. States are derived systematically, with each cell in the grid representing a distinct state of the finite automaton. The intuitive visualization and systematic derivation of transitions between states are facilitated by the spatial representation of the grid. This approach allows for the creation of both DFA and NFA, with the flexibility to incorporate additional states, such as dead or trap states, as needed for DFA. The Grid Automata method provides a flexible framework for addressing a wide range of computational challenges, ensuring correctness and efficiency in automata design. This visualization is shown in the following Fig. 2. Advances in Technology Innovation, vol. 9, no. 3, 2024, pp. 239-255 243 Fig. 2 Visualization of Grid Automata method 3.1.1. Algorithm 1: construction of Finite Automata using Grid Automata method This algorithm presents a revolutionary approach to generating Finite Automata using the Grid Automata method, an innovative framework that improves automata construction efficiency and scalability. The distinctive contribution is the combination of grid-based computations with classical automata theory, resulting in a more robust and adaptable solution for complicated state transition systems. This method dramatically improves computing efficiency by utilizing spatial data structures found in grid systems, lowering temporal complexity compared to older methods. Furthermore, the technique enables better viewing and manipulation of state transitions, which is especially useful for applications that require real-time system updates. Input: Finite Automaton specification (Q, Σ, δ, q0, F) Output: Deterministic finite automaton (DFA) or nondeterministic finite automaton (NFA) Procedure: (1) Initialize input alphabet: Initialize the input alphabet Σ (2) Determine states: Determine the total number of states required for the Finite Automaton. This is typically based on the size of the input alphabet Σ and any additional constraints or conditions: Let m be the number of states for a condition and n be the number of states for another condition. Total number of states = m × n. (3) Organize the states into a grid pattern: Construct an mxn matrix grid where ‘m’ denotes the number of rows and ‘n’ signifies the number of columns. Alternatively, create a nxm matrix grid if needed (transpose matrix). (4) Assign state identifiers: Label each cell with a unique state identifier. (5) Define transition function δ: Determine the transitions between states based on the input alphabet Σ and the language pattern or condition. Define transitions for each cell in the grid, considering both row-wise and column-wise transitions. If constructing a DFA, consider introducing a dead or trap state if necessary to handle undefined or unexpected inputs. This dead state ensures that the automaton transitions to a non-accepting state for inputs not explicitly defined in the transition function. (6) Determine initial state and accepting states: Set the initial state as the starting point. Identify the accepting states based on the language pattern or condition. (7) Construct Finite Automaton: Combine the organized grid layout with the defined transition function, initial state, and accepting states. (8) Validate automata: Test the automaton with representative input strings to verify its behavior and adherence to the language pattern or condition. (9) Refine grid layout or transition function (if necessary): Address any discrepancies or errors identified during validation. (10) Finalization: Once validated, the constructed finite automaton is ready for use in recognizing strings that conform to the specified language pattern or condition. End of Algorithm 1 244 Advances in Technology Innovation, vol. 9, no. 3, 2024, pp. 239-255 Example 1: Consider language L over the alphabet {a, b}, defined as: L = {w ∈ {a, b}* | na(w) mod 3 = 0 and nb(w) mod 2 = 0} This means that the number of occurrences of ‘a’ in a string is divisible by 3, and the number of occurrences of ‘b’ is divisible by 2. (1) Initialize input alphabet: Σ = {a, b} (2) Determine states: m: The number of states for ‘a’ is 3, n: The number of states for ‘b’ is 2, So the total number of states = m × n = 3 × 2 = 6. (3) Organize the states into a grid pattern: Create a m × n = 2 × 3 grid pattern to represent the states. Each cell in the grid corresponds to a unique state of the finite automaton. (4) Assign state identifiers: Label each cell in the grid with a unique state identifier. Steps 3 and 4 are shown in the following Fig. 3. Fig. 3 Grid pattern with assigned identifiers for states (5) Define transition function δ: To determine the transition function for the given example, it will divide it into two parts: Divisibility by 3 (Strings with ‘a’), denotes the state as q0, q1, q2 in the first row and q3, q4, q5 in the second row. The transitions are as follows: δ(q0, a) = q1, δ(q1, a) = q2, δ(q2, a) = q0, δ(q3, a) = q4, δ(q4, a) = q5, δ(q5, a) = q3 These transitions are shown in the following Fig. 4. Fig. 4 Transitions for divisibility by 3 (Strings with ‘a’) Divisibility by 2 (strings with ‘b’), denotes the states as q0, q3 in the first column, q1, q4 in the second column, and q2, q5 in the third column. The Transitions are as follows: δ(q0, b) = q3, δ(q1, b) = q4, δ(q2, b) = q5, δ(q3, b) = q0, δ(q4, b) = q1, δ(q5, b) = q2 These transitions are shown in the following Fig. 5. Fig. 5 Transitions for divisibility by 2 (Strings with ‘b’) Advances in Technology Innovation, vol. 9, no. 3, 2024, pp. 239-255 245 (6) Determine initial state and accepting states: Set the initial state as the starting point of the automata. The final states of the Finite Automata accept strings where the number of occurrences of ‘a’ is divisible by 3 and the number of occurrences of ‘b’ is divisible by 2 which means the final state that accepts strings with ‘a’ such that the number of occurrences of ‘a’ modulo 3 equals 0, and ‘b’ modulo 2 equals 0, would be identified as an accepting state. Here the final state is q0 for the given example is shown in the following Fig. 6. Fig. 6 Final states for accepting strings with divisibility conditions (7) Construct Finite Automaton: Combine the organized grid layout with the defined transition function, initial state, and accepting states to construct the finite automaton. For this language, both DFA and NFA are equivalent, as there are no dead states and each symbol allows for only a single transition, ensuring determinism in both models. The final automata is shown in Fig. 7. After transposing, the resulting n × m matrix or 3 × 2 matrix represents the same finite automaton as the original m × n matrix, ensuring equivalence in their functionality and language recognition capabilities. This automaton is shown in the following Fig. 8. Fig. 7 Constructed Finite Automaton with Grid Automata method Fig. 8 Equivalence of transposed and original grid automaton (8) Validate automata: The constructed Finite Automaton undergoes thorough testing using sample input strings to confirm its functionality and adherence to language criteria. Valid inputs, such as {“ε”, “a3”, “b2”, “a6”, “aaabb”, “ababa”, “aabbbbaaaa”}, demonstrate its ability to recognize compliant strings. Conversely, invalid inputs, like {“a”, “b”, “ab”, “aaab”, “aabbb”, “aaabbba”}, validate its rejection of non-conforming strings. (9) Refine grid layout or transition function (if necessary): Post-validation, the automaton undergoes meticulous evaluation, refining its layout or transition function for improved accuracy and efficiency, ensuring alignment with language pattern. (10) Finalization: With validation and refinement complete, the finite automaton is primed for real-world deployment, offering dependable language processing capabilities. End of Example 1 246 Advances in Technology Innovation, vol. 9, no. 3, 2024, pp. 239-255 After studying the Grid Automata algorithm and providing an example, a concise algorithm is derived for constructing Finite Automata using the Grid Automata method. This shortened algorithm aims to provide a quick overview of the key steps involved. 3.1.2. Algorithm 2: construction of Finite Automata using Grid Automata method (summarized approach) The aforementioned approach encapsulates the key breakthroughs of the Grid Automata method for building Finite Automata. The fundamental contribution is a streamlined process that considerably decreases computing overhead while ensuring excellent accuracy and consistency in automata production. This method stands out because it provides a simple yet powerful tool for automata construction, demonstrating the progress in grid-based automata theory. The summary approach focuses on how the strategy may be effectively applied to a variety of real-world settings, displaying versatility and adaptability. Furthermore, it gives a direct comparison to existing methodologies, emphasizing the gains in efficiency and reliability that the methodology brings to the area. Input: Finite Automaton specification (Q, Σ, δ, q0, F) Output: Deterministic finite automaton (DFA) or nondeterministic finite automaton (NFA) Procedure: (1) Initialize input alphabets. (2) Define the matrix structure. (3) Construct a Finite Automaton for one condition, then balance it with others. (4) Set the first state as initial and determine the final state according to the conditions. Add a trap state if needed to handle undefined or unexpected inputs. (5) Validate Finite Automaton with representative strings. End of Algorithm 2 Different automata types, such as at least, atmost, and exactly conditions, can be easily designed using the Grid Automata method. From Table 1, it is determined that a total number of states is required, ensuring precise automata construction for accurate language recognition. Table 1 Rules for determining the total number of states in Grid Automata Condition Automata type Rules for DFA (total states) Rules for NFA (total states) Atleast Single alphabet (n + 1) (n + 1) Atmost Single alphabet (n + 2) (n + 1) Exactly Single alphabet (n + 2) (n + 1) At least All alphabets (n + 1) × (m + 1) (n + 1) × (m + 1) At most All alphabets (n + 1) × (m + 1) + 1 (n + 1) × (m + 1) Exactly All alphabets (n + 1) × (m + 1) + 1 (n + 1) × (m + 1) Example 2: Consider the language L over the alphabet {a, b}, defined as: L = {w∈{a, b} ∗ ∣ na(w) ≥ 3 and nb(w) ≥ 2} The language L consists of all strings over the alphabet {a, b} where the number of occurrences of ‘a’ is at least 3 and the number of occurrences of ‘b’ is at least 2. (1) Initialize input alphabets: Σ = {a, b} (2) Define matrix structure: total number of states using the formula: (n + 1) × (m + 1) = (3 + 1) × (2 + 1) = 4 × 3 = 12. Hence, a 4 × 3 matrix can be created to represent the states. (3) Construct Finite Automaton for one condition, then balance with others: Construct Finite Automaton by adding transitions for ‘a’ to ensure at least 3 ‘a’'. Refer to the following Fig. 9 for the transitions involving ‘a’. Balance the Finite Automaton with transitions for ‘b’ to ensure at least 2 ‘b’. Ensure that the final automaton, balanced with ‘b’, accepts strings meeting both conditions. Refer to the following Fig. 10 for the final balanced automaton. Advances in Technology Innovation, vol. 9, no. 3, 2024, pp. 239-255 247 (4) Set the first state as initial and determine the final state according to the conditions. Add a trap state to handle undefined or unexpected inputs: Initial state = q0. No trap state is needed as DFA and NFA are equivalent for this language. The final Finite Automaton represents the synchronized behavior of both conditions, ensuring compliance with the language pattern. Here the final state is q11. (5) Validate Finite Automaton with representative strings: Test the Finite Automaton with both accepted and rejected representative strings to verify its behavior: Accepted strings: {“aaaabb”, “abaaaabbb”, “aabbaaaab”, “abbaa”} Rejected strings: {“ab”, “aabbb”} These steps demonstrate the construction and validation of a finite automaton using the Grid Automata method for the language where the number of ‘a’s is atleast 3 and the number of ‘b’s is atleast 2. End of Example 2 Fig. 9 Initial automaton for at least 3 ‘a’ Fig. 10 Final balanced automaton for at least 3 ‘a’ and at least 2 ‘b’ Example 3: Design DFA for the language L over the alphabet {a, b}, defined as: L = {w ∈ {a, b} ∗ ∣na(w) ≤ 3 and nb(w) ≤ 2} The language L consists of all strings over the alphabet {a, b} where strings consist of ‘a’s and ‘b’s, with the condition that the number of ‘a’s does not exceed 3 and the number of ‘b’s does not exceed 2. (1) Initialize input alphabets: Σ = {a, b} (2) Define matrix structure: Calculate total nos of states using the formula: (n + 1) × (m + 1) = (3 + 1) × (2 + 1) = 4 × 3 = 12. Hence, a 4 × 3 matrix can be created to represent the states. (3) Construct Finite Automaton for one condition, then balance with others: Construct Finite Automaton by adding transitions for ‘a’ to ensure at most 3 ‘a’. Refer to the following Fig. 11 for the transitions involving ‘a’. Balance the Finite Automaton with transitions for ‘b’ to ensure atmost 2 ‘b’. Ensure that the final automaton, balanced with ‘b’, accepts strings meeting both conditions. Refer to the following Fig. 12 for the final balanced automaton. (4) Set the first state as initial and determine the final state according to the conditions. Add a trap state if needed to handle undefined or unexpected inputs. Initial state = q0. Trap state = q12. No trap state is needed as both DFA and NFA are equivalent for this language. The final Finite Automaton represents the synchronized behavior of both conditions, ensuring compliance with the language pattern. Here the final states are {q0, q1, q2, q3, q4, q5, q6, q7, q8, q9, q10, q11}. (5) Validate Finite Automaton with representative strings: Test the Finite Automaton with both accepted and rejected representative strings to verify its behavior: Accepted strings: {“ε”, “a”, “b”, “aa”, “ab”, “ba”, “aaa”, “aab”, “aba”, “baa”, “abb”, “bab”} 248 Advances in Technology Innovation, vol. 9, no. 3, 2024, pp. 239-255 Rejected strings: {“aaaa”, “aaaaa”, “aaaaaa”, “aaaab”, “aabaa”, “bbb”, “bbbb”, “babab”, “ababab”} These steps demonstrate the construction and validation of a finite automaton using the Grid Automata method for the language where the number of ‘a’s is at most 3 and the number of ‘b’s is at most 2. End of Example 3 Fig. 11 Initial automaton for atmost 3 ‘a’ Fig. 12 Final balanced automaton for atmost 3 ‘a’ and atmost 2 ’b’ Example 4: Design DFA for the language L over the alphabet {a, b}, defined as: L = {w ∈ {a, b} ∗ ∣ na(w) = 3 and nb(w) = 2} The language L consists of all strings over the alphabet {a, b} where strings contain exactly 3 'a's and 2 'b's. (1) Initialize input alphabets: Σ = {a, b} (2) Define the matrix structure: Total number of states using the formula: (n + 1) × (m + 1) = (3 + 1) × (2 + 1) = 4 × 3 = 12. (3) Construct Finite Automaton for one condition, then balance with others: Construct Finite Automaton by adding transitions for ‘a’ to ensure exactly 3 ‘a’. Refer to the following Fig. 13 for the transitions involving ‘a’. Balance the Finite Automaton with transitions for ‘b’ to ensure exactly 2 ‘b’. Ensure that the final automaton, balanced with ‘b’, accepts strings meeting both conditions. Refer to the following Fig. 14 for the final balanced automaton. (4) Set the first state as initial and determine the final state according to the conditions. Add a trap state if needed to handle undefined or unexpected inputs. Initial state = q0. Trap state = q12. No trap state is needed as DFA and NFA are equivalent for this language. Advances in Technology Innovation, vol. 9, no. 3, 2024, pp. 239-255 249 The final Finite Automaton represents the synchronized behavior of both conditions, ensuring compliance with the language pattern. Here the final state is q11. (5) Validate Finite Automaton with representative strings: Test the Finite Automaton with both accepted and rejected representative strings to verify its behavior: Accepted strings: {“aaabb”, “abaab”, “aabab”, “ababa”, “baaab”, “baaba”, “babaa”, “aabba”, “abbaa”, “bbaaa”} Rejected strings: {“aaaab”, “aaaaa”, “aaaaaa”, “aabbb”, “abbbb”, “bbbb”, “bbbbb”, “babab”, “bbaab”} These steps demonstrate the construction and validation of a finite automaton using the Grid Automata method for the language where the number of ‘a’s is exactly 3 and the number of ‘b’s is exactly 2. End of Example 4 Fig. 13 Initial automaton for exactly 3 ‘a’. Fig. 14 Final balanced automaton for exactly 3 ‘a’ and 2 ‘'b’ 3.2. Product Automata Product Automata is a method that analyzes complex systems by integrating multiple automata into a single automaton. This method utilizes the Cartesian product combine multiple automata into one, synchronizing their transitions between states [12-15]. By using this method, it becomes easier to understand complex systems by breaking them down into parts and synchronizing their behavior. Product Automata enables a comprehensive study of system-wide properties and interactions and are particularly useful for analyzing systems with multiple components or subsystems. This visualization is shown in the following Fig. 15. 250 Advances in Technology Innovation, vol. 9, no. 3, 2024, pp. 239-255 Fig. 15 Product Automata State Construction 3.2.1. Algorithm 3: construction of Product Automata In this section, a groundbreaking algorithm is presented for building Product Automata that takes advantage of the developed techniques to efficiently integrate several automata into a coherent Product Automaton. The main contribution is the development of a systematic strategy to improve the accuracy and performance of Product Automata building, which is distinguished by this work’s new combination of increased state synchronization and transition management strategies. The suggested method not only streamlines the merging process but also assures that the resulting automaton is optimized for minimal state redundancy and maximum transition efficiency. This development is especially significant in applications like parallel processing and complicated system simulations, where maintaining peak performance is critical. Input: Two Finite Automata FA1 and FA2, denoted as (Q1, Σ1, δ1, q01, F1) and (Q2, Σ2, δ2, q02, F2) respectively. Output: Product Automata represents the synchronized behavior of FA1 and FA2. Procedure: (1) Define Finite Automata: Let FA1 and FA2 be the given Finite Automata. (2) Determine state space: Combine the state spaces to obtain Q = Q1 × Q2. (3) Define input alphabet: Set the input alphabet as Σ = Σ1 ∪ Σ2. (4) Combine transition functions: Define the transition function as δ((q1, q2), a) = (δ1(q1, a), δ2(q2, a)), where a ∈ Σ. (5) Set initial state: Determine the initial state as q0 = (q01, q02). (6) Determine accepting states: Use union condition: F = {(q1, q2) ∣ q1 ∈ F1 or q2 ∈ F2} if either of FA1 or FA2 recognizes the strings. (7) Construct Product Automata: Combine state space, input alphabet, transition function, initial state, and accepting states to create the Product Automaton representing the synchronized behavior of FA1 and FA2. End of Algorithm 3 Let’s now explore multiple examples to demonstrate the versatility of the Product Automata construction algorithm. Example 5: Consider the two Finite Automata FA1 and FA2, over the alphabet {a, b}, recognizing the following languages: FA1: L1 = {w ∈{a, b} ∗ ∣ na(w) is even} FA2: L2 = {w ∈{a, b} ∗ ∣ nb(w) is even} (1) Define Finite Automata: Let FA1 represent the Finite Automaton for the language where the number of occurrences of ‘a’ is even, and FA2 represents the Finite Automaton for the language where the number of occurrences of ‘b’ is even. Fig. 16 and Fig. 17 illustrate FA1 and FA2 respectively. Fig. 16 Finite Automata FA1 with even occurrences of ‘a’ Fig. 17 Finite Automata FA2 with even occurrences of ‘b’ Advances in Technology Innovation, vol. 9, no. 3, 2024, pp. 239-255 251 (2) Determine state space: Combine the state spaces to obtain Q = {A, B} × {C, D} = {AC, AD, BC, BD}. (3) Define input alphabet: Set the input alphabet as Σ = {a, b}. (4) Determine state space: Define the transition function as follows: δ((q1, q2), a) = (δ1(q1, a), δ2(q2, a)) δ((q1, q2), b) = (δ1(q1, b), δ2(q2, b)) Refer to Fig. 18 for a visual representation of the transition function. Fig. 18 Transition Function for Product Automata with even occurrences of ‘a’ and ‘b’ (5) Set initial state: Determine the initial state as q0 = (q01, q02) = (A, C). (6) Determine accepting states: Using intersection conditions: F = {(q1, q2) ∣ q1 ∈ F1 and q2 ∈ F2}, where F1 = {A} and F2 = {C}. (7) Construct Product Automaton: Combine state space, input alphabet, transition function, initial state, and accepting states to create the Product Automaton representing the synchronized behavior of FA1 and FA2, as depicted in Fig. 19. The Product Automata FAProduct will accept strings where both the number of ‘a’s and ‘b’s are even: L = L1 ∩ L2 = {w ∈ {a, b} ∗ ∣ na(w) is even and nb(w) is even}. Fig. 19 Product Automata for even occurrences of ‘a’ and ‘b’ End of Example 5 Example 6: Consider the two Finite Automata FA1 and FA2, over the alphabet {a, b}, recognizing the following languages: FA1: L1 = {w ∈ {a, b} ∗ ∣ na(w) mod 4 = 0} FA2: L2 = {w ∈ {a, b} ∗ ∣ nb(w) mod 3 = 0} (1) Define Finite Automata: Let FA1 represent the Finite Automaton for the language where the number of occurrences of 252 Advances in Technology Innovation, vol. 9, no. 3, 2024, pp. 239-255 ‘a’ is divisible by 4, and FA2 represent the Finite Automaton for the language where the number of occurrences of ‘b’ is divisible by 3. Refer to Fig. 20 and Fig. 21 for visual representations of FA1 and FA2, respectively. Fig. 20 Finite Automata FA1 with ‘a’ occurrences divisible by 4 Fig. 21 Finite Automata FA2 with ‘b’ occurrences divisible by 3 (2) Determine state space: Combine the state spaces to obtain Q = {A, B, C, D} × {E, F, G} = {AE, AF, AG, BE, BF, BG, CE, CF, CG, DE, DF, DG}. (3) Define input alphabet: Set the input alphabet as Σ = {a, b}. (4) Determine state space: Define the transition function as follows: δ((q1, q2), a) = (δ1(q1, a), δ2(q2, a)), δ((q1, q2), b) = (δ1(q1, b), δ2(q2, b)) Refer to Fig. 22 for a visual representation of the transition function. Fig. 22 Transition Function for Product Automata with ‘a’' mod 4 = 0 and ‘b’ mod 3 = 0 (5) Set initial state: Determine the initial state as q0 = (q01, q02) = (A, E). (6) Determine accepting states: Using intersection conditions: F = {(q1, q2) ∣ q1 ∈ F1 and q2 ∈ F2}, where F1 = {A} and F2 = {E}. (7) Construct Product Automaton: Combine state space, input alphabet, transition function, initial state, and accepting states to create the Product Automaton representing the synchronized behavior of FA1 and FA2, as depicted in Fig. 23. Product Automata FAProduct will accept strings where both numbers of ‘a’s are divisible by 4 and several ‘b’s is divisible by 3: L = {w ∈ {a, b} ∗ ∣ na(w) mod 4 = 0 and nb(w) mod 3 = 0} End of Example 6 Advances in Technology Innovation, vol. 9, no. 3, 2024, pp. 239-255 253 Fig. 23 Product Automata for ‘a’ mod 4 = 0 and ‘b’ mod 3 = 0 4. Experimental Result The performance of this developed method is compared with other conventional techniques in terms of construction time, memory utilization, scalability, robustness, application range, and complexity measures available in the literature. Time complexity is measured by �� ∗ ��_��_�ℎ��� where is the length of the pattern and ��_��_�ℎ�� is the size of the alphabet. Scalability is measured using � ∗ �� technique [16] that is available in the literature. The robustness of the algorithms is calculated by the finite order linear time-invariant (LTI) [17] model found in the literature. This study assessed grid and Product Automata techniques for Finite Automata construction, focusing on accuracy, precision, and computational efficiency across scenarios. Results show significant improvements over conventional methods by following in Table 2, rated on a scale of 0 to 100%. Higher values indicate better scalability, robustness, and application range, while lower values are preferred for construction time, memory usage, and complexity. This comparison is based on experiments with Finite Automata-related datasets. Table 2 Comparison of the developed technique with conventional methods Criteria Developedevelope techniques Conventional methods Improvement Construction time 90% 40% 50% Memory utilization 80% 30% 50% Scalability 95% 50% 45% Robustness 90% 60% 30% Application range 95% 40% 55% Complexity 85% 60% 25% Fig. 24 shows a detailed performance metrics comparison between the developed techniques and conventional methods. The developed techniques show a 50% improvement in construction time to build automata, which can be highly effective. Memory usage also has been improved by 50%, demonstrating better resource utilization. The experiments result in up to 45% improvement in scalability demonstrating that overall larger and more complicated automata can be handled by the derived methods. Robustness can be quantitatively measured to evaluate how stable and reliable the methods are, which could be improved by 30%. The increase in the application range is 55% which indicates that techniques are applicable in a moderate number of scenarios. Lastly, these approaches reduce complexity by 25% more than existing traditional methods and are easier to deploy. 254 Advances in Technology Innovation, vol. 9, no. 3, 2024, pp. 239-255 Fig. 24 Graphical representation of performance comparison between developed and conventional methods 5. Conclusion In this study, the exploration was centered on elucidating the construction of Finite Automata using two distinct methodologies: Grid Automata uses a structured grid-like arrangement of states to enable systematic state transitions. In contrast, Product Automata combines numerous automata into a single framework to coordinate their behaviors to expedite computing processes. The assessment indicated significant advantages of these approaches over conventional methods. Grid Automata’s systematic arrangement improves the clarity and speed of state transitions, whereas Product Automata allows for the aggregation of multiple automata, resulting in more streamlined and synchronized behavior. The performance evaluation produced promising results. In terms of construction time, memory utilization, scalability, robustness, application range, and complexity, the methodologies consistently outperformed traditional techniques by 25% to 50%. This demonstrates the practical viability and superiority of Grid and Product Automata for developing Finite Automata. This study advances automata theory and emphasizes the practical application of these approaches in various disciplines. Grid and Product Automata show promise for future applications in natural language processing, pattern recognition, compiler design, robotics, and bioinformatics because they simplify complex computational problems while providing stable and scalable solutions. As computational systems improve, integrating these strategies promises more efficient and effective problem-solving ways. This developed automated system’s scalability will benefit industries such as vehicle manufacturing and logistics in the future. Let’s look at some more future automation possibilities. This developed method will significantly impact the robotics business in the coming years, facilitating the development and assembly of advanced robots. Additionally, this approach will play a significant part in the field of self-driving cars, a growing focus in technology. Conflicts of Interest The authors declare no conflict of interest. References [1] X. Zhao, D. Shi, Y. Li, F. Qin, Z. Chu, and X. Yang, “Simulation of Dynamic Recrystallization in 7075 Aluminum Alloy Using Cellular Automaton,” Journal of Wuhan University of Technology-Mater. Sci. Ed., vol. 39, no. 2, pp. 425- 435, April 2024. [2] O. Amir, A. Amir, A. Fraenkel, and D. Sarne, “On the Practical Power of Automata in Pattern Matching,” SN Computer Science, vol. 5, no. 4, article no. 400, April 2024. [3] A. Modanese and T. Worsch, “Embedding Arbitrary Boolean Circuits Into Fungal Automata,” Algorithmica, in press. https://doi.org/10.1007/s00453-024-01222-7 Advances in Technology Innovation, vol. 9, no. 3, 2024, pp. 239-255 255 [4] G. Pighizzini, L. Prigioniero, and S. Sadovsky, “Performing Regular Operations With 1-Limited Automata,” Theory of Computing Systems, vol. 68, no. 3, pp. 465-486, June 2024. [5] A. Maletti and A. T. Nasz, “Weighted Tree Automata With Constraints,” Theory of Computing Systems, vol. 68, no. 1, pp. 1-28, February 2024. [6] G. R. Laura, J. M. Francisco, G. S. Manuela, R. A. Pedro, and M. F. Víctor, “Cellular Automata Simulations of the Sintering Behavior of Ceramics Driven by Surface Energy Reduction,” Natural Computing, vol. 23, no. 1, pp. 69-70, March 2024. [7] P. Kishore, N. Thaduru, and K. K. Srinivas, “Design of High Performance Adders Using Quantum Dot Cellular Automata (QCA),” 14th International Conference on Computing Communication and Networking Technologies, pp. 1- 6, July 2023. [8] B. Shahid, A. U. Rehman, N. Tahir, and O. Sattar, “Active Strategy for Learning Non-Deterministic Automata by Peer,” International Conference on Business Analytics for Technology and Security, pp. 1-7, March 2023. [9] V. Jaiswal and T. N. Sasamal, “A Novel Approach to Design Multiplexer Using Magnetic Quantum-Dot Cellular Automata,” IEEE Embedded Systems Letters, vol. 15, no. 3, pp. 133-136, September 2023. [10] V. Havlena, P. Matousek, O. Rysavy, and L. Holík, “Accurate Automata-Based Detection of Cyber Threats in Smart Grid Communication,” IEEE Transactions on Smart Grid, vol. 14, no. 3, pp. 2352-2366, May 2023. [11] P. Battyányi, T. Mihálydeák, and G. Vaszil, “Rough-Set-Like Approximation Spaces for Formal Languages,” Journal of Automata, Languages and Combinatorics, vol. 27, no. 1-3, pp. 79-90, 2022. [12] R. Vogrin, R. Meolic, and T. Kapus, “Generating and Employing Witness Automata for ACTLW Formulae,” IEEE Access, vol. 10, pp. 9889-9905, 2022. [13] S. Krehlik, “n-Ary Cartesian Composition of Multiautomata With Internal Link for Autonomous Control of Lane Shifting,” Mathematics, vol. 8, no. 5, article no. 835, May 2020. [14] M. Dutta, S. Kalita, and H. K. Saikia, “Cartesian Product of Automata,” Advances in Mathematics: Scientific Journal, vol. 9, no. 10, pp. 7915-7924, 2020. [15] M. Novak, S. Krehlik, and D. Stanek, “n-Ary Cartesian Composition of Automata,” Soft Computing, vol. 24, no. 3, pp. 1837-1849, February 2020. [16] X. Yu, W. C. Feng, D. Yao, and M. Becchi, “O3FA: A Scalable Finite Automata-Based Pattern-Matching Engine for Out-Of-Order Deep Packet Inspection,” Proceedings of the 2016 Symposium on Architectures for Networking and Communications Systems, pp. 1-11, March 2016. [17] S. Zekraoui, N. Espitia, and W. Perruquetti, “Finite-Time Estimation of Second-Order Linear Time-Invariant Systems in the Presence of Delayed Measurement,” International Journal of Robust and Nonlinear Control, vol. 33, no. 15, pp. 8951-8976, October 2023. Copyright© by the authors. Licensee TAETI, Taiwan. This article is an open-access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY-NC) license (https://creativecommons.org/licenses/by-nc/4.0/).