当前位置：网站首页>3.9 - 正规表达式和正规集 3.10 - 有限自动机

3.9 - 正规表达式和正规集 3.10 - 有限自动机

2022-08-09 23:33:00 【是李黏黏鸭】

目录

一、正规表达式和正规集

1、关于正规表达式和正规集的描述

2、考法1：理解正规表达式的含义

二、有限自动机

1、分类

2、确定有限自动机

3、非不确定有限自动机

4、图解有限自动机

5、考法1：有限自动机可识别字符序列

一、正规表达式和正规集

1、关于正规表达式和正规集的描述

2、考法1：理解正规表达式的含义

二、有限自动机

1、分类

  • 确定有限自动机

  • 不确定有限自动机

2、确定有限自动机

  • 如果输入给定值a，它的状态一定转移，那么就是确定自动机。

3、非不确定有限自动机

  • 输入字符后，状态可能转移，也有可能不转移，这就是非确定自动机。

4、图解有限自动机

S0：标表示初始。

两个圈：表示结束。

（1）

  • 由图可知，字符串一定是以“abb”结尾的。

  • S0输入a可能转移到S1，也可能返回本身S0，所以可在S0处输入多个a才能转移到S1。

  • S0输入b返回S0，但是不确定前面有几个a.

  • 所以图中对应的正规式为：

（2）

  • S0输入a一定转移到状态S1，所以字符串是以a开头的。

  • S1处不确定要输入多少个b，可能是0个，也可能是n个。

  • S1输入a一定转移到状态S2，所以字符串是以a结尾的。

  • 所以图中对应的正规式为：

5、考法1：有限自动机可识别字符序列

原网站

版权声明
本文为[是李黏黏鸭]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_46071165/article/details/126240126

边栏推荐

猜你喜欢

随机推荐