定義
形式系統(Formal System),,包含字母,字的集合及由關係組成的有限集合.例如:集合論,布林代數,歐幾里得平面幾何及貝克式正規形式(Backus Normal Form;BNF)都是形式系統.
用途
對於程式語言的設計,實施及研究等方面而言,形式系統扮演的角色越來越重要.語法規格,語言結構分析
語言相關的說明
語言可以視為一群句子或公式的集合(即成串的符號),它具有定義良好的(Well-defined)結構而且通常是有
意義
語言的語法(syntax)是由定義該語言合法結構的原則所組成,亦即語言的語法用來描述於言的格式(form).大部分的語言都包含無限個合法句字,而將所有合法句子都儲存起來是不可能的
利用一列舉式演算法(listing algorithm)來產生合法字串
對於任一合法的字串都能經由演算法有限次的列舉產生,這個列舉演算法稱為語言的產生規格.
語言相關說明
若一語言的所有字串經由產生句子之演算法有限個步驟處理後都能決定是否合法,則此語言稱為可決定的(decidable).英文太含糊而且易導致定義不明確,不宜用英語正視地定義語言.
需要發展一形式語言來描述語言的定義,這個描述語言定義的語言稱為語法的中間語言.(syntatic meta-language)
形式語言
形式語言是一種中間語言被描述的語言稱為目的語言(object language),它的符號稱為終端符號(terminal symbols).
描述語言的符號稱為非終端符號(nonterminal symbols)
Finite State Machine
在有限狀態機(Finite State Machine,FSM),或稱為有限自動機(Finite Automata)中
有某些狀態Si (State Si)被設定為可接受的(Acceptable)狀能.
如果有一輸入字串(String)經一連串的推移(Transite)後,恰好到達可接受的狀態Si(Acceptable State),則稱此一字串為合法字串(Legal String);否則稱之為不合法字串(Illagal String).
所有可被此FSM接受的字串所成之集合,稱此集合為可被此FSM認知(Recognized)的語言(Language).
三大城市的出色的
FSM
Example例101001與0101皆可被此有限狀態機接受,但0111則不能被此有限狀態機所認知(Recognize).此有限狀態機所能認知的語言為1*010*1.
:可接受的狀態Si(Acceptable State)稱之為終止狀態(Final State),一般以 表示.
Si
設 I為一輸入集(Input Set),則正規表示式(Regular Expression)定義為:
法則1: 為一個正規表示式,寫成{ },即表示含空字串之語言.
法則2: c I,為一個正規表示式,寫成,即表示僅含有一個文字(包括數字)的語言.
法則3:若S與R為兩個正規表示式,它們分別表示LR與LS兩種語言,則
Regular Expression
Regular Expression(cont'd)(1) (R)│(S)的正規表示式表示(LR LS) .
(2) (R).(S)的正規表示式表示(LR.LS) .
(3) (R)*的正規表示式表示LR*.
a*表示 ,a,aa,aaa,…
a+表示a,aa,aaa,…
a|b表示可為a或b."|"或以"V"表示之;相當於
OR.故(a|b)*可為abab,aaab,bbbbb,….
所有正規表示式可以表現的字串集合稱(Regular Set).
亦可用 表示.
Example
10*1*相對的regular set 為
{1, 10, 101, 1001, 11, 111, …}
Grammar
G被稱為文法(Grammar),若G=,其中N為非終端符號(Nonterminal )的集合.
T為終端符號(Terminal)的集合.
為開始(Start)符號, N.
P為產生規則之集合,如 ,其中 , (N T)*, ;即 不可為空字串.
N T= .
: 開始符號(Start Symbol) 有些是以S表示.
一般非終端符號均以大寫的英文字母表示,終端符號
則符號則以小寫的英文字母表示.
Grammar(cont'd)
Example
N={A, B, }, T={a, b}
P: Ab, A Ba, B b, B Bb
其所能認知的語言
Ab Bab … Bbnab bbnab bn+1ab
b+ab
所對應之FSA
Grammar(cont'd)
四種型態的語言及其所對應之文法與機器
Type 0:其對應的文法為沒有限制的文法 (Unrestricted Grammar).其產生規則(Product Rule)沒有任何的限制.
Type 1:其所對應的文法為與內容有關的文法(Context Sensitive Grammar).其產生規則會與上下有關,即在產生規則 1 2 1 2 中, 之左邊必須 1且其右邊必須為 2時,才會衍生出 1 2.並限制產生規則右邊所有符號的長度必須大於或等於左邊所有符號的長度.
Grammar(cont'd)
Type 2:其所應的文法為與內容無關的文法 (Gontext Free Grammar).其產生規則與上下文無關,但限制產生規則之左邊僅能有一個非終端符(Nonterminal Symbol).
Type 3:其所對應的文法為正規文法(Regular Grammar).其產生規則限制產生規則左邊與右最多只能有一個非終端符號,並且產生規則的右邊也僅能有一個終端符號.
Backus Normal Form
BNF (Backus Normal Form 或Backus Naur Form)描述法自從Backus 與Naur創建BNF描述法定義了ALGOL 60的構文(Syntax)以來,許多計算機語言都採用BNF 描述法來描述程式語言.
BNF所使用的符號
"│"表示"或(or)."
"::="表示"定義為(Define as)."
"被所括住者"表示"終端符號(Terminal Symbol)" .
"沒有被所括住者"表示"終端符號(Terminal Symbol)".
例:::=0│1 2 3 4 5 6 7 8 9
Backus Normal Form(cont'd)
::=A B C D E F G H I J K L
M N O P Q R S T U M W
X Y Z
::=
BNF 僅可描述 Type 2之文法(即Context Free Grammar).
BNF 之優點:
明確且易懂.
較易於建構有效的剖析程式(Parser).
較易將程式翻譯成機器碼及易於偵測出錯誤.
DFA, NFA
一個有限自動機(Finite Automata)若其對於每一個輸入符號(Input symbol)有唯一狀態轉變(State Transition),則稱此自動機為決定性的有限自動機(Deterministic Fintie Automata,DFA).
若每一個狀態Si(State Si)在接受一個輸入符號後,可以有兩種以上的狀態轉變,如Si a Sj ,Si a Sk,則稱此自動機為非決定性的有限自動機(Non-deter-ministic Finite Automata,NFA).
一個NFA一定可以化簡成一個DFA.
DFA, NFA(cont'd)
Regular Expression NFA
將正規表示式(Regular Expression)轉化成NFA之演算法.輸入:定義於文字集(N T)上之正規表示式R.
輸出:一個可以接受正規表示式R所定義之語言的NFA.
(1)對 所建立的NFA.
(2)對終端符號中a所建立的NFA為
每次需要一個新的狀態(State)時,則給此新的狀態一個新的編號,則不會有兩個狀能具有相同的編號.
Regular Expression NFA(cont'd)
Regular Expression NFA(cont'd)
(3)利用上述兩種基本正規表示式(Basic Regular Expression)的NFA建構法,則可用此兩者將複合正規表示式(Compound Regular Expression) 建構成NFA.根據下述的轉換規則便可順利的將正規表示式R建立成一個完整的NFA.
首先,必須立一個初始狀態(Initial State)Si及一個終止狀態(Final State) Sf.
若是有R1│ R2這類型的複合正規表示式,則所建構的NFA如下:
Regular Expression NFA(cont'd)
若是有R1 R2這類型的複合正規表示式,則所建構的NFA如下:
Regular Expression NFA(cont'd)
若是有R1*這類型的複合正規表示式,則所建構的NFA如下:
Regular Expression NFA(cont'd)
例:將正規表示式R=(0│1)*01轉換成NFA.
首先分解正規表示式R為基本成分如下:依據上圖之架構分別求其基本NFA(Primitive NFA)與複合NFA(Compound NFA).
Regular Expression NFA(cont'd)
(1)對第一個基成分(Primitive Component) R1,即對第一個終端符號0所建構之基本NFA如下:
(2)同理,對R2所建構之基本NFA為:
Regular Expression NFA(cont'd)
(3)對R3= R1│ R2所建構之複合NFA如下:
(4)因為R4=(R3),所以R4之NFA與R3之NFA完全相同.
Regular Expression NFA(cont'd)
(5)對R5= R4*所建構之複合NFA如下:
Regular Expression NFA(cont'd)
(6)對R6=0所建構之基本NFA如下:
:取用狀態7'是便於稍後合併時無需再修改其他狀態之值.
Regular Expression NFA(cont'd)
(7) R7= R5 R6所建構之基本NFA如下:
:狀態7與狀態7'合併成狀態7.
Regular Expression NFA(cont'd)
(8)重上述之步驟,建構R9=(0│1)*01之NFA如下:
NFA DFA
一般Input Symbol含有 (空字串)者
Step 1:一個名為N之NFA欲化為名為D之DFA, D之初始狀態(initial state)是包含初狀態s0之集合,故將此state s0加入 -CLOSURE(s0)中,從s0可經由input symbol為 而到達之state均加入此 -CLOSURE(s0)中,此集合即為此DFA之initial state,設其為marked state .
Step 2: 對已marked state中元素,對每一input symbol a( ) si marked state,若f(si, a)=sj,將所有成集合T而 -CLOSURE(T),若不等於已有的state,則設為unmarked state.
Step 3:尋找下一個unmarked state,設其為marked stated,重複step ,直到無unmarked state為止.
NFA DFA
NFA DFA
Step 4: 由上述步驟可求得一個Transition Table,若其含原NFA之initial state(or finial state),則此state就是initial state(or finial state) .
Step 5:依Transition Table求Transition diagram即為所求.
NFA DFA
NFA DFA
NFA DFA
NFA DFA
NFA DFA
NFA DFA
NFA DFA
NFA DFA
NFA DFA
NFA DFA
由NFA轉換所得之DFA,其中的某些態可以再合併成為一個狀態,至於如何將DFA之狀態數最小化(Minimize)其處理方式有下述三個步驟:
步驟一:將DFA中所有狀態所形成之狀態群(Group)G分割成終止狀態群F與非終止狀態群(G-F).
步驟二:藉由下述之分裂程式(Procedure SPLIT)對所有的狀態群做分裂(Split)處理.任一狀態群若因分裂程式處理而產生狀態群分裂,則繼續對該分裂之獎態群做分裂處理,直至所有的狀態群皆無法再分裂為止.
DFA 最小化
DFA 最小化(cont'd)
步驟三:令每個狀態群為一個新的狀態(State).
步驟四:刪除所有的死亡狀態(Dead States);即該狀態非初始狀態,而且無法自其他狀態到達之狀態.
DFA 最小化(cont'd)
Procedure SPLIT
begin
for each group G of P do
begin
partition G into subgroups such that two states s and t of G are
in the same subgroup if and only for all input symbol a, states s
and t have transitions to states in the same group of P;
replace all subgroups that formed in P;
end
end
DFA 最小化(cont'd)
Example
DFA 最小化(cont'd)
DFA 最小化(cont'd)
步驟一:將狀態A,B,C,D,E分割成非終止狀態群{A,B,C,D}與終止狀態群.
步驟二:由於終止狀態群僅含有一個狀態E,故無須再分裂.狀態{A,B,C,D}經分裂程式處理,得知狀態A,B,C,D對輸入符號0皆轉移(Transite)至狀態B(屬於同一狀態群{A,B,C,D}中).但對於輸入符號1而言,狀態群{A,B,C,D}中僅有狀態D會轉移至狀態群,而狀態A,B,C則均會轉移至狀態群{C,D}中,故將狀態群{A,B,C,D}分裂成{A,B,C}與兩個狀能群.由於狀態群僅含有一個狀態D,故無須再分裂.再對狀態群{A,B,C}做分裂處理,對於輸入符號0狀態A,B,C均轉移至狀態B,但對輸入符號1,僅有狀態B會轉移至狀態D(即狀態群中),故再將狀態群{A,B,C}分裂成{A,C},.至此,無法再分裂了.
DFA 最小化(cont'd)
步驟三:令每一個狀態群為一新的狀態.
{A,C}=S1
令{A,C}=S1
= S2
= S3
= S4
步驟四:無任何死亡狀態,故不須刪除任何一個狀態.
由上可得到的轉移表(Transition Table)為
最後,求得最小狀態數之DFA為
FA Regular Grammar
將有限自動機(Finite Automata)轉成正規文法(Regular Grammar)之方法:
(1)若狀態A對於輸入的終端符號a會到達狀能B,而且狀態B並非終止狀態(Final State),則其正規文法為A aB.
(2)若狀態A對於輸入的終端符號a會到達狀態B,而且狀態(Final State),則其正規文法A a, A aB.
(3)若狀態A對於輸入的終端符號a會到達狀態A本身,而且狀態A既是初始狀態(Initial State)亦是終止狀態,則其正規文法為A ,A a與A aA.
例:
則其正規文法為G=,N={S,A,B,C},T={0,1},P={
S , A 0C, B 0C, C 0C,
S 0, A 1C, B 1B, C 1C}
S 0A, B 1,
S 1,
S 1B,
根據上面之文法,可求得相對應之語言為L(G)={0,1*}.
