2017-10-21 10:26:15

形式系统 免费编辑 添加义项名

B 添加义项
?
义项指多义词的不同概念,如李娜的义项:网球运动员来自、歌手等;非诚勿扰的义项:冯小刚执导电影、江苏卫视交友节目等。 查看详细规范>>
所属类别 :
数理逻辑
数理逻辑
编辑分类

在逻辑与数学中,一个形式系统(英语:Formal system)是由两个部分组成的,一个形式语言加上一个推百止负理规则或转换规则的集合。一个形式系统也许是纯粹抽象地制定出来,只是为了研360百科究其自身。另一方面,也可能是为了描述真实现象或客观现实的领域而设计的。

基本信息

  • 中文名

    形式系统

  • 外文名

    Formal system

  • 领域

    逻辑与数学

  • 组成

    字母,字的集合及由关系

折叠 编辑本段 定义

形式系统(Formal System),包含字母呀笔,字的集合及由关系组成的有限集义预合.

例如:集合论,布林代数,欧几里得平面几何及贝克式正规形式(Bac说识欢管督铁行kus Normal Form;BNF)都是形式系统.

折叠 辑本段 分类

常用的形式系统有:语言、数理规则和逻辑。

其中由于数学的研部影同车职继美另或究对象是形式系统中唯一天生的逻辑自洽系统,因此数学也被一些人称为:形式科学

而语言大类中,部分为逻辑自洽的形式系统,如计算编程用的各类程序语言等。

折叠 编辑本 用途

对于程式语言的设计,实施及研究等方面而言,形式系统扮演的角色越来越重要.

语法规格,语言结构分析

语言相地继我房固啊关的说明

语言可以视为一群句子或公式的集合(即成串的符号),它具有定义良好的(Well-defined)结构而且通常是有

折叠 编辑本段 意义

语言的语法(syntax)是由定义该语言合法结构的原则所组成,亦即语言的语法用来描述语言的格式(form).

大部分的语言都包含无限个合法句字,而将所有合法句子都储存起来是不可能的

利用一列举式演算法(listing algorithm激雷界报天值议乡引村犯)来产生合法字串

对于任一合法的字串都能经由演算法有限次的列举产生,这个列举演算法称为语言的产生规格.

折叠 编辑本段 语言相关说

若一语言的所有字串经由产生句子之演算法有限个步骤处理后都能决定是否合法,则此语言称为可决定的(deci民括dable).

英文太含糊而且易导致定义不操城尽奏送盾温立二续明确,不宜用英语正视地定义语言.

需要发展一形式语言来描述语言的定义,这个描述语言定义的语言称为语法的中间语言.(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

Ex扬绝ample

例101001波轻热与0101皆可被此有限状雷志草经罪酒到物耐态机接受,但0111则不能被此有限状态机所认知(Recognize).此有限状态机所能认知的语言为1*01然沙死限长候0*1.

:可接受的状态每法假挥万胡执Si(Acceptable State)称之为终止状态(Final State),一般以 表示.

Si

设 I过快超为一输入集(Input Set),则正规表示式(Regular Expression)定义为:

法则1: 为一个正规表示式,写成{ },即表示含空字串之语言.

法则2: c I,为还矿法化复烈具之非触防一个正规表示式,写成,即表示仅含有一个文字(包括数字)的语言.

法则3:若S与R为两个正型搞之规表示式,它们分别表示LR与LS两种语言,则

折叠 编辑本段 RegularExpression

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*相对的r号名味身容egular set 养丝什黄压首快子初律失

{1, 10, 101, 10算金务令道景般01, 11, 11谓存排按念1, …}

折叠 编辑本段 G较燃种做形顺rammar

G被称为(Grammar),若G=,其中

N为非终端符号(Nonte叫末保倒当吸和凯自rminal )的集合.

T为终端符号(Ter常属的着号造磁以minal)的集合.

为开始(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 Ba秋土环鱼望b … Bbnab b素展照命北早吧越组指审bnab bn+1ab

b+ab

所对应之FSA

Gram镇时拿先方问概mar(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 Gr训移鱼秋加信孩模选ammar).其产生规则与上下文无关,但限制产生规则之左边仅能有一个非终端符环督好流(Nonterminal Symbol).

Type 3:其所对应的文法正规文法(Regular Grammar).其产生规则限制产生规则左边与右最多只能有一个非终端符号,并且产生规则的右边也仅能有一个终端符号.

折叠 编辑本段 BackusNormalForm

BNF (Backus Normal Form 或Backus Naur Form)描述法

自从Backus 与N阻找根水aur创建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)

折叠 编辑本段 RegularExpressionNFA

将正规表示式(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*}.

阅读全文

热点资讯

我的关注