Probabilistic automata and stochastic languages

• Main Author: Soh, Royson Jun Heng
• Other Authors: Wu Guohua
• Format: Final Year Project
• Language: English
• Published: Nanyang Technological University 2024
• Subjects: Mathematical Sciences
• Online Access: https://hdl.handle.net/10356/175632
• Institution: Nanyang Technological University

This paper explores into probabilistic automata and stochastic languages, which serves as an overview to its concepts. Probabilistic Automata, which is a generalisation of nondeterministic finite automata, will be the main focus in this paper. We shall study the mathematical foundations, concepts and properties of Probabilisitic Automata and the languages recognised by these automata. We will also study the link between finite automata and probabilistic automata, and see some applications. We start by discussing finite automata, then regular language. We will understand the limitation on how these automata failing to capture probabilistic features. This limitation allow us to see the introduction of probabilistic automata. We will explore further into transition probabilities, operations and acceptance criteria. We will then look into stochastic languages, and its applications. There are many real-world applications, such as speech recognition and protocol verification, that we can model using probabilistic automata.