有穷自动机能识别什么定义的语言
发布网友
发布时间：2022-04-29 04:59
共1个回答
热心网友
时间：2022-06-19 00:05
有穷自动机能够识别上下文无关语言。
拓展资料：有穷自动机，或有穷状态的机器，是描述（或“机器”）特定类型算法的数学方法。特别地，有穷自动机可用作描述在输入串中识别模式的过程，因此也能用作构造扫描程序。
当然有穷自动机与正则表达式之间有着很密切的关系，在下一节中大家将会看到如何从正则表达式中构造有穷自动机。但在学习有穷自动机之前，先看一个说明的示例。
通过下面的正则表达式可在程序设计语言中给出标识符模式的一般定义（假设已定义了letter 和digit）：
identifier = letter ( letter | digit ) *
它代表以一个字母开头且其后为任意字母和/ 或数字序列的串。
有穷自动机
通过标明数字1 和2 的圆圈表示的是状态（state），它们表示其中记录已被发现的模式的数量在识别过程中的位置。带有箭头的线代表由记录一个状态向另一个状态的转换（transition），该转换依赖于所标字符的匹配。
有穷自动机又分为确定型的有穷自动机（DFA）与非确定型的有穷自动机（NFA）两种。
