形式系統(tǒng)，是完全形式化的系統(tǒng)，用形式語言表述，這是現代公理系統(tǒng)的趨勢，是不同于古典公理系統(tǒng)之處。
系統(tǒng)定義
形式系統(tǒng)(Formal System),,包含字母，字的集合及由關系組成的有限集合.
例如：集合論，布林代數，歐幾里得平面幾何及貝克式正規(guī)形式(Backus Normal Form;BNF)都是形式系統(tǒng).
系統(tǒng)用途
對于程式語言的設計，實施及研究等方面而言，形式系統(tǒng)扮演的角色越來越重要.
語法規(guī)格，語言結構分析
語言相關的說明
語言可以視為一群句子或公式的集合(即成串的符號),它具有定義良好的(Well-defined)結構而且通常是有
研發(fā)意義
語言的語法(syntax)是由定義該語言合法結構的原則所組成，亦即語言的語法用來描述于言的格式(form).
大部分的語言都包含無限個合法句字，而將所有合法句子都儲存起來是不可能的
利用一列舉式演算法(listing algorithm)來產生合法字串
對于任一合法的字串都能經由演算法有限次的列舉產生，這個列舉演算法稱為語言的產生規(guī)格.
語言相關說明
若一語言的所有字串經由產生句子之演算法有限個步驟處理后都能決定是否合法，則此語言稱為可決定的(decidable).
英文太含糊而且易導致定義不明確，不宜用英語正視地定義語言.
需要發(fā)展一形式語言來描述語言的定義，這個描述語言定義的語言稱為語法的中間語言.(syntatic meta-language)
形式語言
形式語言是一種中間語言
被描述的語言稱為目的語言(object language),它的符號稱為終端符號(terminal symbols).
描述語言的符號稱為非終端符號(nonterminal symbols)
Finite State Machine
在有限狀態(tài)機(Finite State Machine,FSM),或稱為有限自動機(Finite Automata)中
有某些狀態(tài)Si (State Si)被設定為可接受的(Acceptable)狀能.
如果有一輸入字串(String)經一連串的推移(Transite)后，恰好到達可接受的狀態(tài)Si(Acceptable State),則稱此一字串為合法字串(Legal String);否則稱之為不合法字串(Illagal String).
所有可被此FSM接受的字串所成之集合，稱此集合為可被此FSM認知(Recognized)的語言(Language).
三大城市的出色的
運用示例
FSM
例101001與0101皆可被此有限狀態(tài)機接受，但0111則不能被此有限狀態(tài)機所認知(Recognize).此有限狀態(tài)機所能認知的語言為1*010*1.
:可接受的狀態(tài)Si(Acceptable State)稱之為終止狀態(tài)(Final State),一般以 表示.
Si
設 I為一輸入集(Input Set),則正規(guī)表示式(Regular Expression)定義為:
法則1: 為一個正規(guī)表示式，寫成{ },即表示含空字串之語言.
法則2: c I,為一個正規(guī)表示式，寫成，即表示僅含有一個文字(包括數字)的語言.
法則3:若S與R為兩個正規(guī)表示式，它們分別表示LR與LS兩種語言，則
Regular Expression
Regular Expression(cont'd)
(1) (R)│(S)的正規(guī)表示式表示(LR LS) .
(2) (R).(S)的正規(guī)表示式表示(LR.LS) .
(3) (R)*的正規(guī)表示式表示LR*.
a*表示 ,a,aa,aaa,…
a+表示a,aa,aaa,…
a|b表示可為a或b."|"或以"V"表示之；相當于
OR.故(a|b)*可為abab,aaab,bbbbb,….
所有正規(guī)表示式可以表現的字串集合稱(Regular Set).
亦可用 表示.
10*1*相對的regular set 為
{1, 10, 101, 1001, 11, 111, …}
Grammar
G被稱為文法(Grammar),若G=,其中
N為非終端符號(Nonterminal )的集合.
T為終端符號(Terminal)的集合.
為開始(Start)符號, N.
P為產生規(guī)則之集合，如 ,其中 , (N T)*, ;即 不可為空字串.
N T= .
: 開始符號(Start symbol) 有些是以S表示.
一般非終端符號均以大寫的英文字母表示，終端符號
則符號則以小寫的英文字母表示.
Grammar(cont'd)
N={A, B, }, T={a, b}
P: Ab, A Ba, B b, B Bb
其所能認知的語言
Ab Bab … Bbnab bbnab bn+1ab
所對應之FSA
Grammar(cont'd)
四種型態(tài)的語言及其所對應之文法與機器
Type 0:其對應的文法為沒有限制的文法 (Unrestricted Grammar).其產生規(guī)則(Product Rule)沒有任何的限制.
Type 1:其所對應的文法為與內容有關的文法(Context Sensitive Grammar).其產生規(guī)則會與上下有關，即在產生規(guī)則 1 2 1 2 中, 之左邊必須 1且其右邊必須為 2時，才會衍生出 1 2.并限制產生規(guī)則右邊所有符號的長度必須大于或等于左邊所有符號的長度.
Grammar(cont'd)
Type 2:其所應的文法為與內容無關的文法 (Gontext Free Grammar).其產生規(guī)則與上下文無關，但限制產生規(guī)則之左邊僅能有一個非終端符(Nonterminal Symbol).
Type 3:其所對應的文法為正規(guī)文法(Regular Grammar).其產生規(guī)則限制產生規(guī)則左邊與右最多只能有一個非終端符號，并且產生規(guī)則的右邊也僅能有一個終端符號.
Backus Normal Form
BNF (Backus Normal Form 或Backus Naur Form)描述法
自從Backus 與Naur創(chuàng)建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).
法國國家圖書館 之優(yōu)點:
明確且易懂.
較易于建構有效的剖析程式(Parser).
較易將程式翻譯成機器碼及易于偵測出錯誤.
DFA, NFA
一個有限自動機(Finite Automata)若其對于每一個輸入符號(Input symbol)有唯一狀態(tài)轉變(State Transition),則稱此自動機為決定性的有限自動機(Deterministic Fintie Automata,DFA).
若每一個狀態(tài)Si(State Si)在接受一個輸入符號后，可以有兩種以上的狀態(tài)轉變，如Si a Sj ,Si a Sk,則稱此自動機為非決定性的有限自動機(Non-deter-ministic Finite Automata,NFA).
一個NFA一定可以化簡成一個DFA.
DFA, NFA(cont'd)
Regular Expression NFA
將正規(guī)表示式(Regular Expression)轉化成NFA之演算法
輸入：定義于文字集(N T)上之正規(guī)表示式R.
輸出：一個可以接受正規(guī)表示式R所定義之語言的NFA.
(1)對 所建立的NFA.
(2)對終端符號中a所建立的NFA為
每次需要一個新的狀態(tài)(State)時，則給此新的狀態(tài)一個新的編號，則不會有兩個狀能具有相同的編號.
Regular Expression NFA(cont'd)
Regular Expression NFA(cont'd)
(3)利用上述兩種基本正規(guī)表示式(Basic Regular Expression)的NFA建構法，則可用此兩者將復合正規(guī)表示式(Compound Regular Expression) 建構成NFA.根據下述的轉換規(guī)則便可順利的將正規(guī)表示式R建立成一個完整的NFA.
首先，必須立一個初始狀態(tài)(Initial State)Si及一個終止狀態(tài)(Final State) Sf.
若是有R1│ R2這類型的復合正規(guī)表示式，則所建構的NFA如下:
Regular Expression NFA(cont'd)
若是有R1 R2這類型的復合正規(guī)表示式，則所建構的NFA如下:
Regular Expression NFA(cont'd)
若是有R1*這類型的復合正規(guī)表示式，則所建構的NFA如下:
Regular Expression NFA(cont'd)
例：將正規(guī)表示式R=(0│1)*01轉換成NFA.
首先分解正規(guī)表示式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如下:
:取用狀態(tài)7'是便于稍后合并時無需再修改其他狀態(tài)之值.
Regular Expression NFA(cont'd)
(7) R7= R5 R6所建構之基本NFA如下:
:狀態(tài)7與狀態(tài)7'合并成狀態(tài)7.
Regular Expression NFA(cont'd)
(8)重上述之步驟，建構R9=(0│1)*01之NFA如下:
NFA DFA
一般Input Symbol含有 (空字串)者
Step 1:一個名為N之NFA欲化為名為D之DFA, D之初始狀態(tài)(initial state)是包含初狀態(tài)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,其中的某些態(tài)可以再合并成為一個狀態(tài)，至于如何將DFA之狀態(tài)數最小化(Minimize)其處理方式有下述三個步驟:
步驟一：將DFA中所有狀態(tài)所形成之狀態(tài)群(Group)G分割成終止狀態(tài)群F與非終止狀態(tài)群(G-F).
步驟二：藉由下述之分裂程序(Procedure SPLIT)對所有的狀態(tài)群做分裂(Split)處理。任一狀態(tài)群若因分裂程序處理而產生狀態(tài)群分裂，則繼續(xù)對該分裂之獎態(tài)群做分裂處理，直至所有的狀態(tài)群皆無法再分裂為止.
DFA 最小化
DFA 最小化(cont'd)
步驟三：令每個狀態(tài)群為一個新的狀態(tài)(State).
步驟四：刪除所有的死亡狀態(tài)(Dead States);即該狀態(tài)非初始狀態(tài)，而且無法自其他狀態(tài)到達之狀態(tài).
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)
DFA 最小化(cont'd)
DFA 最小化(cont'd)
步驟一：將狀態(tài)A,B,C,D,E分割成非終止狀態(tài)群{A,B,C,D}與終止狀態(tài)群.
步驟二：由于終止狀態(tài)群僅含有一個狀態(tài)E,故無須再分裂。狀態(tài){A,B,C,D}經分裂程序處理，得知狀態(tài)A,B,C,D對輸入符號0皆轉移(Transite)至狀態(tài)B(屬于同一狀態(tài)群{A,B,C,D}中).但對于輸入符號1而言，狀態(tài)群{A,B,C,D}中僅有狀態(tài)D會轉移至狀態(tài)群，而狀態(tài)A,B,C則均會轉移至狀態(tài)群{C,D}中，故將狀態(tài)群{A,B,C,D}分裂成{A,B,C}與兩個狀能群。由于狀態(tài)群僅含有一個狀態(tài)D,故無須再分裂。再對狀態(tài)群{A,B,C}做分裂處理，對于輸入符號0狀態(tài)A,B,C均轉移至狀態(tài)B,但對輸入符號1,僅有狀態(tài)B會轉移至狀態(tài)D(即狀態(tài)群中),故再將狀態(tài)群{A,B,C}分裂成{A,C},.至此，無法再分裂了.
DFA 最小化(cont'd)
步驟三：令每一個狀態(tài)群為一新的狀態(tài).
{A,C}=S1
令{A,C}=S1
= S2
= S3
= S4
步驟四：無任何死亡狀態(tài)，故不須刪除任何一個狀態(tài).
由上可得到的轉移表(Transition Table)為
最后，求得最小狀態(tài)數之DFA為
FA Regular Grammar
將有限自動機(Finite Automata)轉成正規(guī)文法(Regular Grammar)之方法:
(1)若狀態(tài)A對于輸入的終端符號a會到達狀能B,而且狀態(tài)B并非終止狀態(tài)(Final State),則其正規(guī)文法為A aB.
(2)若狀態(tài)A對于輸入的終端符號a會到達狀態(tài)B,而且狀態(tài)(Final State),則其正規(guī)文法A a, A aB.
(3)若狀態(tài)A對于輸入的終端符號a會到達狀態(tài)A本身，而且狀態(tài)A既是初始狀態(tài)(Initial State)亦是終止狀態(tài)，則其正規(guī)文法為A ,A a與A aA.
例:
則其正規(guī)文法為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*}.
參考資料 >