资源描述：
《自动机运用实例》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、形式语言与自动机运用实例潘主强学号：201421000558形式语言与口动机理论来源于Chomsky对口然语言的研究和ALG0L60语言的语法描述方式。形式语言与自动机理论主要用于：1）给出语言的语法描述方式；2）由文法得到的正文符合文法规范的句了；3）通过程序的词法分析得到编译器所需的结构分析；4）通过二义性检查来保证程序被计算机接受的唯一分析。有限状态自动机确定型（DFA）不确定型（NFA）■确定有限自动机在BBS信息监测系统屮的运用■不确定有限自动机（DNA）基因网络中的应用确定有限自动机在BBS信息监测系统中的运用■确定的有限口动机（DFA）定义：确定的有限自
2、动机（DFA）是一个五元组M二（Q,S,8,qO,F）其中Q：有限状态集，》：字母表,qOWQ是初始状态,FUQ是终止状态集，5：QXE^Q称为状态转换函数。•电子公告栏系统相关介绍:电了公告栏系统(BulletinBoardSystem,简称BBS)乂称电了布告栏系统，它来源于Linux的FireBird系统，它是建立在互联网上，面向公众，提供发布公共消息、聊天、信件服务等功能，满足用户获取信息、交流情感等要求的信息服务系统。BBS信息监测系统主要是针对当前BBS系统中出现危害国家安全、社会稳定而开发的能过滤BBS中的机密、敏感、不良信息的系统。系统采用自动机的理论
3、，创建匹配信息树，对信息进行分析、处理。对于有限口动机儿对于待监测的字符串5-5152-5)7,初始时，有限自动机A处于开始状态和，从左至右逐个扫描字符串S；在6(加，sl)=a的作用下，有限自动机外处于状态刃；在(al,52)=日2的作用下，有限自动机力处于状态旳…。当扫描进入某一个特定的接收状态，即为检测到某不良信息。当扫描结束，若接收机处于初始状态，则表明该字符串未有不良信息存在。下面举出具体的例子说明，定义有限状态接收权U为:5（a0,同）=al5（小，性）=。28（al,倾）=a35（a3,向）=°43（a2f恋）=a55（a4,好）=a66（a5f好）=
4、d6可以得出右线形文法为:dOT同alalT性a2°2~＞倾°3a3T向a4ci29恋a5a4T好a6假如有如下的待检测字符“我认为同性恋好”和S2=“我认为同性相斥”。$推导的过程如下：我）=aO5（d0,认）=aOd（aQf为）=aO5（dO,同）=al8（a,性）=°28（al,恋）=a5好）=a6最后处于最终状态亦，表明该字符串的检测命中，字符串中出现了符合有限自动机推理的信息。再如S2的推导：3（aOt我）=aOS（aOfik）=aO8（a0,为）=aO3（aOf同）=川6（alf性）=a28（u2f相）二aO6（a0,斥）=d0最终处于状态创，这表明该字
5、符串的检测未命中。从上述例子可以看出，这种推理方式可以避免一些词汇的误命中。建立在BBS服务器上的系统采用一个比较小的词典在BBS系统后台运行，直接对出现的明显的色情、反动字眼进行删除。建立在终端上的系统实时的对BBS系统进行检测，一旦发现问题，可以立即报告。而建立在备份服务器上的系统对整个系统进行完全的、彻底的检查。这样的方式最大限度避免了各自的问题，发挥了各自的优点。检测系统中运用形式语言与自动机理论，使用有限状态接收机模型，BBS信息监测系统对照监测字典中的字符信息，对文本内容进行分析、匹配，获取监测结果。■成效:系统具有3个模块，分别为服务器后台监控组件、终端
6、实时监控组件、备份服务器完全检测组件。通过对三个组件的结合使用，BBS信息监测系统达到服务器负荷10%以下，终端监测系统负荷在30%以下。不良信息平均监测时间30s,命中率在90%以上。系统在实践中对BBS系统的信息进行监测，得到了良好的效果，对敏感信息的分析、监测，都达到了系统设计的要求，BBS站的管理屮发挥了重要作用。定义：不确定型的有限自动机(NFA)是一个五元组M二(Q,S,5,qO,F)其中Q:有限状态集，工：字母表,qO£Q是初始状态,FCQ是终止状态集，5状态转换函数.背景：基因调节机制是一个非常复杂的过程。生物信号通过一对•的调节机制逐渐地被转移和扩散
7、到下游基因，从而达到调控基因表达的目的。从细胞生物学的观点来看，基因表达水平影响基因调节过程。在不同的基因调节机制下，基因表达水平的表达水平也不尽相同。正常细胞屮的基因通过多步调节机制来控制细胞生长、差异、重生和细胞凋亡过程。癌症是由于许多外界因素导致基因调节机制的改变。基于传统的观点，基因的调节状态可以被简化地归为激活和抑制两类。传统电子计算机产生的随机数是伪随机数，因而其随机算法不是严格意义上的随机计算。由于生化反应的随机性，随机分子生物计算机比确定性分子生物计算机更适合解决随机性问题。将不确定DNA有限状态自动机应用于基因表达网络，分析基因表达
