自动机理论

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

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

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

有一些在自动机中很重要且经常使用的基本术语：

符号：

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

例：

1，a，b，

字母：

字母是一组有限的符号。用∑表示。

例子：

∑ = {a, b}

∑ = {A, B, C, D}

∑ = {0, 1, 2}

∑ = {0, 1, ....., 5]

∑ = {#, β, Δ}

串：

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

范例1：

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

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

范例2：

w = 010

Number of Sting |w| = 3

语言：

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

范例：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