计算理论笔记 2-非正则语言,乔姆斯基范式
因为0的个数和1的个数要保持一致,所以沿途要记录0的个数与1的个数的差,每个差值对应都要一个状态,而这个值可能是无限的,所以无法用有穷状态机表示。(D中01和10最多差1,所以是正则的)
All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Comment
因为0的个数和1的个数要保持一致,所以沿途要记录0的个数与1的个数的差,每个差值对应都要一个状态,而这个值可能是无限的,所以无法用有穷状态机表示。(D中01和10最多差1,所以是正则的)