自动机理论

自动机理论是计算机科学和数学的一个理论分支。 它研究抽象机器以及可以使用这些机器解决的计算问题。 抽象机器称为自动机。 开发自动机理论的主要动机是开发描述和分析离散系统动态行为的方法。

此自动机由状态和转换组成。 状态用圆圈表示，转换用箭头表示。

自动机是一种机器，它将一些字符串作为输入，并且该输入经过有限数量的状态，并可能进入最终状态。

以下是自动机中重要且常用的基本术语

符号

符号是实体或单个对象，可以是任何字母、字母表或任何图片。

示例

1, a, b, #

字母

字母表是符号的有限集合。 它用 ∑ 表示。

示例

String

它是来自字母表的符号的有限集合。 字符串用 w 表示。

示例 1

如果 ∑ = {a, b}，则可以从 ∑ 生成的各种字符串是 {ab, aa, aaa, bb, bbb, ba, aba.....}。

• 符号出现零次的字符串称为空字符串。 它用 ε 表示。
• 字符串 w 中的符号数称为字符串的长度。 它用 |w| 表示。

示例 2

语言

语言是适当字符串的集合。 在 Σ 上形成的语言可以是有限的或无限的。

示例：1

L1 = {Set of string of length 2}

     = {aa, bb, ba, bb}          Finite Language

示例：2

L2 = {Set of all strings starts with 'a'}

     = {a, aa, aaa, abb, abbb, ababb}         Infinite Language