Visual Execution and Validation of Finite-State Machines and Pushdown Automata

• URL: http://arxiv.org/abs/2508.03641v1
• Date: Tue, 05 Aug 2025 16:54:01 GMT
• Title: Visual Execution and Validation of Finite-State Machines and Pushdown Automata
• Authors: Marco T. Morazán, David Anthony K. Fields, Andrés M. Garced, Tijana Minić,
• Abstract summary: In Formal Languages and Automata Theory courses, students find understanding nondeterministic finite-state and pushdown automata difficult.<n>We present two novel dynamic visualization tools for FSM to support the design of such machines.<n>These tools visualize all computations that may be performed, respectively, by a nondeterministic finite-state machine or by a pushdown automata in a stepwise manner.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In Formal Languages and Automata Theory courses, students find understanding nondeterministic finite-state and pushdown automata difficult. In many cases, this means that it is challenging for them to comprehend the operational semantics of such machines and, as a consequence, determine why a word is accepted or rejected. This is not entirely surprising, because students are mostly trained to design and implement deterministic programs. Comprehension of pushdown automata is further complicated, because reasoning about the stack is necessary. A common difficulty students face, for example, is understanding that two different computations on the same word may reach the same state with different stack values. To aid student understanding, we present two novel dynamic visualization tools for FSM -- a domain-specific programming language for the Automata Theory classroom -- to support the design of such machines. These tools visualize all computations that may be performed, respectively, by a nondeterministic finite-state machine or by a pushdown automata in a stepwise manner. In addition, these tools aid the machine verification process by allowing users to visually validate whether the properties a state represents hold when a machine transitions into it.

Related papers

• Design Support for Multitape Turing Machines [0.0]
  Many Formal Languages and Automata Theory courses introduce students to Turing machine extensions.<n>One of the most widely-used extensions endows Turing machines with multiple tapes.<n>Students find multitape Turing machines no less challenging.
  arXiv  Detail & Related papers  (2025-08-05T16:53:19Z)
• NNTile: a machine learning framework capable of training extremely large GPT language models on a single node [83.9328245724548]
  NNTile is based on a StarPU library, which implements task-based parallelism and schedules all provided tasks onto all available processing units.<n>It means that a particular operation, necessary to train a large neural network, can be performed on any of the CPU cores or GPU devices.
  arXiv  Detail & Related papers  (2025-04-17T16:22:32Z)
• (How) Do Language Models Track State? [50.516691979518164]
  Transformer language models (LMs) exhibit behaviors that appear to require tracking the unobserved state of an evolving world.<n>We study state tracking in LMs trained or fine-tuned to compose permutations.<n>We show that LMs consistently learn one of two state tracking mechanisms for this task.
  arXiv  Detail & Related papers  (2025-03-04T18:31:02Z)
• Counting Reward Automata: Sample Efficient Reinforcement Learning Through the Exploitation of Reward Function Structure [13.231546105751015]
  We present counting reward automata-a finite state machine variant capable of modelling any reward function expressible as a formal language. We prove that an agent equipped with such an abstract machine is able to solve a larger set of tasks than those utilising current approaches.
  arXiv  Detail & Related papers  (2023-12-18T17:20:38Z)
• To Do or Not to Do: Semantics and Patterns for Do Activities in UML PSSM State Machines [0.11470070927586014]
  DoActivity behaviors describe behavior that is executed independently from the state machine once entered in a given state. The specification or textbooks are vague about how the doActivity behavior construct should be appropriately used. We analyzed the semantics by collecting evidence from cross-checking the text of the specification, its semantic model and executable test cases, and the simulators supporting PSSM.
  arXiv  Detail & Related papers  (2023-09-26T12:30:51Z)
• Guess & Sketch: Language Model Guided Transpilation [59.02147255276078]
  Learned transpilation offers an alternative to manual re-writing and engineering efforts. Probabilistic neural language models (LMs) produce plausible outputs for every input, but do so at the cost of guaranteed correctness. Guess & Sketch extracts alignment and confidence information from features of the LM then passes it to a symbolic solver to resolve semantic equivalence.
  arXiv  Detail & Related papers  (2023-09-25T15:42:18Z)
• A Survey on Brain-Inspired Deep Learning via Predictive Coding [85.93245078403875]
  Predictive coding (PC) has shown promising performance in machine intelligence tasks.<n>PC can model information processing in different brain areas, can be used in cognitive control and robotics.
  arXiv  Detail & Related papers  (2023-08-15T16:37:16Z)
• Unsupervised Automata Learning via Discrete Optimization [7.06671668667062]
  We propose a framework for learning a deterministic finite automaton (DFA) from a given multi-set of unlabeled words.<n>We show that this problem is computationally hard and develop three learning algorithms based on constraint optimization.<n>We introduce novel regularization schemes for our optimization problems that improve the overall interpretability of our DFAs.
  arXiv  Detail & Related papers  (2023-03-24T16:19:15Z)
• AI2: The next leap toward native language based and explainable machine learning framework [1.827510863075184]
  The proposed framework, named AI$2$, uses a natural language interface that allows a non-specialist to benefit from machine learning algorithms. The primary contribution of the AI$2$ framework allows a user to call the machine learning algorithms in English, making its interface usage easier. Another contribution is a preprocessing module that helps to describe and to load data properly.
  arXiv  Detail & Related papers  (2023-01-09T14:48:35Z)
• Automated Graph Machine Learning: Approaches, Libraries, Benchmarks and Directions [58.220137936626315]
  This paper extensively discusses automated graph machine learning approaches. We introduce AutoGL, our dedicated and the world's first open-source library for automated graph machine learning. Also, we describe a tailored benchmark that supports unified, reproducible, and efficient evaluations.
  arXiv  Detail & Related papers  (2022-01-04T18:31:31Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  This work proposes a formal definition of statistically meaningful (SM) approximation which requires the approximating network to exhibit good statistical learnability. We study SM approximation for two function classes: circuits and Turing machines.
  arXiv  Detail & Related papers  (2021-07-28T04:28:55Z)
• Induction and Exploitation of Subgoal Automata for Reinforcement Learning [75.55324974788475]
  We present ISA, an approach for learning and exploiting subgoals in episodic reinforcement learning (RL) tasks. ISA interleaves reinforcement learning with the induction of a subgoal automaton, an automaton whose edges are labeled by the task's subgoals. A subgoal automaton also consists of two special states: a state indicating the successful completion of the task, and a state indicating that the task has finished without succeeding.
  arXiv  Detail & Related papers  (2020-09-08T16:42:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.