是一个五元组:
$$
\begin{align}M=(S,∑,σ,S_0,Z)\end{align}
$$
\begin{align}M=(S,∑,σ,S_0,Z)\end{align}
$$
-
S是一个有限集,每个元素为一个状态
-
∑是一个有穷字母表,每个元素为一个输入字符
-
σ是转换函数:是一个单值对照
-
S_0属于S,是其唯一的初态
-
Z是一个终态集(可空)
图中可以识别 10, 11(0|1) , 01, 00(011)这些串
正规式
是描述程序语言单词的表达式,对于字母∑,其上的正规式及其表示的正规集可以递归定义如下
仅有限次使用上述三个步骤定义的表达式才是∑的正规式,闭包运算符‘*’最高优先级,‘|’最低优先级
[解]:C
A->B->C->B->C
其正规式:
$$
\begin{align} (1^*00^*(101)^*1)^* \end{align}
$$
\begin{align} (1^*00^*(101)^*1)^* \end{align}
$$