正则和自动机

正则语言的归纳定义

• $ϵ$是正则语言，用$L(\cdot )$表达正则语言所能识别的集合，则$L(ϵ)=\varnothing$
• $c\in \Sigma$，则$c$是正则语言，$L(c)=\{c\}$
• $r_1$和$r_2$是正则语言，则$r_1{r}_2$是正则语言，$L(r_1{r}_2)=\{ab|a\in L(r_1),b\in L(r_2)\}$
• $r$是正则语言，则$r\ast$是正则语言，$L(r\ast )={\{}^{\prime \prime },a_1,a_1{a}_2,a_1{a}_2{a}_3\dots |a_i\in L(r)\}$
• $r_1$和$r_2$是正则语言，则$r_1|r_2$是正则语言，$L$