定義：
一個擴展有限狀態(tài)機M是一個五元組<S,s0,Σ,Χ,T>。其中：
l S是狀態(tài)的有限集合；
l s0∈S是初始狀態(tài)；
l Σ是有限的字符表；
l X=(x1,x2,…,xk)是一個向量，表示一個變量的有限集合；
l T：對于T中任意一個元素t，t=<s,i,P,A,s’>。其中 s是變遷的起始狀態(tài)，I是輸入，P是變遷的條件(它是由X中的變量或者常數(shù)參與的邏輯表達式)，A是變遷的動作（它是X中的變量或者常數(shù)參與的，對X中的變量的賦值語句集合），s’是變遷的到達狀態(tài)。
當M處于某一個狀態(tài)s的時候，收到一個輸入i，如果存在一個t∈T與s、I對應，并且使P的值為真，則M執(zhí)行A中的動作并移到狀態(tài)s’。
同樣可以證明，EFSM的描述能力與FSM相同。但這個過程同樣碰到狀態(tài)爆炸的問題。