论文部分内容阅读
<正>1 w-E则语言与McNaughton定理令∑={0,1} 我们用∑~*,∑~w分别表示∑上的有限字和w-字所构成的集合.我们把空字记作λ.给定u∈∑~*,N∈∑~w,有时也把u、v分别记为u(0)u(1)…u(n)(若(u)=n+1)和刚v(0)v(1)v(2)….用w(m,n)记字w的从第m个位置起到第n个位置止的那一串符号构成的字.根据McNaughton的定理,w-E则语言可以通过非决定性的B(?)chi自动机来定义,也可以通过决定性的Muller自动机来定义.