有限自动机

本文概述

  • FA的正式定义
  • 有限自动机模型
  • 自动机的类型
  • 有限自动机用于识别模式。
  • 它以符号字符串作为输入,并相应地更改其状态。找到所需符号后,便会发生过渡。
  • 在过渡时,自动机可以移至下一个状态或保持相同状态。
  • 有限自动机有两种状态,接受状态或拒绝状态。当成功处理输入字符串并且自动机达到其最终状态时,它将接受。
FA的正式定义有限自动机是5元组(Q,∑,δ,q0,F)的集合,其中:
Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function

有限自动机模型有限自动机可以用输入磁带和有限控制来表示。
【有限自动机】输入胶带:它是具有一定数量单元的线性胶带。每个输入符号放置在每个单元格中。
有限控制:有限控制在从输入磁带接收特定输入时决定下一个状态。磁带读取器从左到右一一读取单元,并且一次只读取一个输入符号。
有限自动机

文章图片
自动机的类型有限自动机有两种类型:
  1. DFA(确定性有限自动机)
  2. NFA(不确定性有限自动机)
有限自动机

文章图片
1. DFA
DFA是指确定性有限自动机。确定性是指计算的唯一性。在DFA中,机器仅针对特定输入字符进入一种状态。 DFA不接受零举动。
2. NFA
NFA代表非确定性有限自动机。它用于为特定输入传输任何数量的状态。它可以接受零位移动。
关于DFA和NFA的一些重要点:
  1. 每个DFA均为NFA,但NFA并非DFA。
  2. NFA和DFA中都可以有多个最终状态。
  3. DFA用于编译器中的词法分析。
  4. NFA更像是一个理论概念。

    推荐阅读