计算理论复习

Author Avatar
Benz 12月 26, 2017

计算理论的复习笔记

自动机

定义

有穷自动机是元祖 \( (Q,\sum, \delta, q_0, F) \)
\( Q :\) 状态集
\( \sum :\) 字母表
\( \delta :\) 转移函数
\( q_0 :\) 起始状态
\( F :\) 接受状态

泵引理

若A是正则语言则存在p使得：如果s是A中任一长度不小于p的字符串，则s可分为三段,即s=xyz，满足

  1. 对于任意 \( i \geq 0 \)有\(xy^i z\)
  2. \(|y| > 0 \)
  3. \(|xy| \leq p\)

专业术语

  • 汉明距离: 非零元素的个数一个字符串中
  • 确定型有穷自动机(DFA)
  • 非确定性有穷自动机(NFA)

上下文无关语法

定义

上下文无关文法是一个四元组 \( (V, \sum, R, S)\)