语言的幂级数表达式和有限自动机状态方程的近似解法

THE POWER SERIES REPRESENTATION OF LANGUAGES AND THE APPROXIMATE SOLUTION OF STATE EQUATION TO THE FINITE AUTOMATA

一、预备知识 具有初始状态和最终状态的有限自动机是一个5维系统。设M=(Q,Σ,q_1,δ,T),其中Σ为输入的有限字母表,Q为有限状态集,q_1,T分别为初始状态和终结状态集合,并且T(?)Q.δ为状态转移函数.δ:Q×Σ→Q 当δ为单值函数时,M为确定有限自动机;如果δ为半序函数时,则M为不完全确定有限自动机。本文讨论不限于确定有限自动机。为方便起见,以下简称M为机器。

A state space approach to the finite automata was proposed by Tony T.Lee in 1983[1].He introduced the φ-representation of Languages and gave the state equation of he finite automata under the condition of Σ={0,1}.This paper extends it to Σ={δ_0,δ_1,…,δ_2m_(-1)}and discusses some properties of the φ-representation, associates it with Kleene's equation and gives a numerical example of recognizabel languages of incompletely specified finite automata