简单百科
形式系统

形式系统

形式系统，是完全形式化的系统，用形式语言表述，这是现代公理系统的趋势，是不同于古典公理系统之处。

系统定义

形式系统(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),一般以表示.

设 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).

法国国家图书馆之优点:

明确且易懂.

较易于建构有效的剖析程式(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)时，则给此新的状态一个新的编号，则不会有两个状能具有相同的编号.