定义：
一个扩展有限状态机M是一个五元组<S,s0,Σ,Χ,T>。其中：
l S是状态的有限集合；
l s0∈S是初始状态；
l Σ是有限的字符表；
l X=(x1,x2,…,xk)是一个向量，表示一个变量的有限集合；
l T：对于T中任意一个元素t，t=<s,i,P,A,s’>。其中 s是变迁的起始状态，I是输入，P是变迁的条件(它是由X中的变量或者常数参与的逻辑表达式)，A是变迁的动作（它是X中的变量或者常数参与的，对X中的变量的赋值语句集合），s’是变迁的到达状态。
当M处于某一个状态s的时候，收到一个输入i，如果存在一个t∈T与s、I对应，并且使P的值为真，则M执行A中的动作并移到状态s’。
同样可以证明，EFSM的描述能力与FSM相同。但这个过程同样碰到状态爆炸的问题。