词，为一无法解释的计算法则或逻辑系统，用途及意义与语言相关说明，形式语言及不同的语言个不同，应视情况用。

定义

用途

意义

语言相关说明

形式语言

FSM

Regular Expression

Grammar

Backus Normal Form

Regular Expression NFA

定义

形式系统(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*}.