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