当前位置: 首页 > 编程日记 > 正文

句法模式识别(两)-正规文法、上下文无关文法

正规的语法特点

1.全部长度有限的语言都是正规的。

2.用正规文法当然能产生无限长串,当中周期反复部分的长度不大于非终止符的长度。

举个样例


在此规则之下。能生成句子

当中周期反复部分为ab,这个样例的非终止符的元素个数为2,故满足2不大于2.

 

自嵌入特性

我们把上下文无关文法中的正规文法去掉。剩下的那部分我们叫做真正的上下文无关文法

自嵌入特性是区分真正的上下文无关文法与正规文法的判定标准

即一个真正的上下文无关文法一定具有自嵌入特性。正规文法具有非自嵌入特性。亦即非自嵌入的上下文无关文法是正规文法。上下文无关文法就蜕化了。

 

 

什么是自嵌入特性?

自嵌入顾名思义,就是可以自己嵌入自己


当然必须保证vx不能是空串

 

uvwxy定理

这是一个用以判定上下文无关文法和正规文法的条件。

就是说,当这个文法满足自嵌入条件,表示出来就是


那么,能够得到


当中vx的反复次数同样且为非空串时,则这个文法肯定就是真正的上下文无关文法。由于这样的周期形式是正规文法所不具有的。比方这样的


就是必需要用真正的上下文无关文法。

 

以下介绍上下文无关文法的等价文法。

不同的上下文无关文法。它们生成的语言有可能是等价的,这样就涉及到一个最优文法的问题。那么最优是什么?最有就是高效、没有冗余和浪费。

 

粗略说有2种冗余,并且仅仅有非终止符可以冗余。终止符总是实用的啦。

其一是浪费环节。

浪费环节是说由单个非终止符传递到了单个的非终止符。比方


这样的形式意味着B是多此一举的。还不如直接A到C呢。

 

其二是无用环节。

细分又有2类。

通俗说

1.无尾的无用非终止符

所谓无尾,就是咱用了这个终止符,话根本都没法结束。

有头无尾。

A根本没法最后变成常量(终止符)。

不存在x使得

 

2.无头的无用非终止符

所谓无头,就是这句话根本就不可能从这个非终止符開始。有尾无头。

从起始符開始根本找不到含有A的句子。

从起始符S開始,不存在

 

首先介绍怎样消去浪费环节。

消去浪费环节包含2个部分。

其一消去。

其二修正。

 

消去过程

这个过程用递归算法来实现。

就是要求出全部非终止符各自相应能到达的全部非终止符集合

 

举个样例就好了


如今消去浪费环节,先考虑S。

发现S能在一步之内的非终止符仅仅有A

在K1(S)集合中再次出发。在一步之内能走到的新非终止符仅仅有B

再往后没有新的非终止符了。

同理考察A,A在一步之内能到达的非终止符仅仅有B了,记

再考察B,B根本就没有能在一步之内能到达的新终止符。

 

于是这相应的3个集合就求完了


 

修正过程

修正过程就依照上面的消去过程打补丁就好了,由于要消去一堆连接。旧桥拆了总得又一次修吧。还是上面那个样例,先把之前的生成关系画出来,如图1黑线所看到的。


图1

如今考虑A,依据集合,我们要去掉A到B的连接

那么就得补上S到b、A到b、S到aS、A到aS。黄线代表。

 

然后再考虑S。要去掉S到A

那么就得补上S到BAb。绿线代表。

 

注意:如今尽管看起来文法规则比曾经更麻烦了,可是,实际生成句子的过程却变得简单了很多,所以简化没简化还是要看疗效。

 

以下介绍消去没用的终止符

消去无用终止符的思路就是。找出全部实用的非终止符,那么剩下的自然就是没实用的了。

 

消去无尾非终止符

找出全部的有尾非终止符集合。定义为J(G)

方法是


这个表达式非常清晰。还是举个样例。反而绕口。但还是举吧



这个表达式事实上是一步步找到那些终于的到达终止符的非终止符

首先J0(G)为空集。

则J1(G)为全部能一步走到以终止符为尾的非终止符,即A

继续,J2(G)是J1(G)并上全部能在一步之内到以J1(G)或者其它终止符为尾的非终止符。

好绕口。。。

事实上就是{S,A}

再往下就找不到了。只是如今忽然发现,B呢?怎么没看到B的影子。

这就说明B就是无尾的无用非终止符

 

去掉全部跟B有过关系的生成关系就好。如今是新的生成关系


 

再说说消去无头非终止符

也是仅仅要找出全部有头的非终止符就好。剩下自然就无头了

用表达式表示是这种


这个表达式的意义事实上就是从起始符,回溯一步步展开,希望能找到句子的头部。

 

还是举个样例


展开起始符S,发现S能到aAA,因此R1(S)={S,A}

A继续展开。发现A能到aCA。因此R2(S)={S,A,C}

搞定,又发现原来B是无头的非终止符,赶紧删掉与它有关系的全部表达关系就好了。不再赘述。

 

上下文无关文法的2中标准型

1.C(Chomsky)标准型


举一个样例马上就知道怎么把随便一个上下文无关文本变成C标准型了:


 

2.G(Greibach)标准型


这个严格的转化方法有点畸形,就临时不展开了。

简单情况用凑的就好了。


欢迎參与讨论并关注本博客微博以及知乎个人主页兴许内容继续更新哦~

转载请您尊重作者的劳动,完整保留上述文字以及本文链接,感谢您的支持!


版权声明:本文博客原创文章,博客,未经同意,不得转载。

转载于:https://www.cnblogs.com/blfshiye/p/4621922.html

相关文章:

6软件测试过程

软件测试过程前言软件测试的几个典型过程总结前言 测试策划、测试设计与实现、测试执行、回归测试和测试总结。 软件测试的几个典型过程 软件测试过程主要包括测试策划、测试设计与实现、测试执行、回归测试和测试总结,每个活动过程中包括的主要工作内容如下图所示…

BFS之三(单向bfs和康托压缩)

//poj 1077 Eight#include <iostream> //单向bfs和康托压缩#include<string>using namespace std;bool visited[1000000];int fac[]{1,1,2,6,24,120,720,5040,40320,362880}; //9!表int cantor(int arr[]) {int temp,num1; //当排列为…

[JavaWeb基础] 007.Struts2的配置和简单使用

1.框架简介 采用Struts能开发出基于MVC(Model-View-Controller)设计模式的应用构架&#xff0c;用于快速开发Java Web应用。Struts实现的重点在C(Controller)&#xff0c;包括ActionServlet/RequestProcessor和我们定制的Action,也为V(View)提供了一系列定制标签&#xff08;C…

使用Rust + Electron开发跨平台桌面应用 ( 一 )

前言 近段时间学习了Rust&#xff0c;一直想着做点什么东西深入学习&#xff0c;因为是刚学习&#xff0c;很多地方都不熟悉&#xff0c;所以也就不能拿它来做编译器这些&#xff0c;至于web开发&#xff0c;实际上我并不建议拿这个来学习一门语言&#xff0c;大概有几个方面&a…

7软件质量与测试规范

软件质量与测试规范 前言标准/规范产品质量模型总结前言 标准和规范可以指导测试工作的方向。 标准/规范 软件质量与测试标准分为国际标准、国家标准、行业标准、企业(机构)规范、项目规范等。下一层标准需要在上一层标准的框架下做扩展或补充。比如行业标准首先要满足国家…

UVa 679 - Dropping Balls

称号&#xff1a;有一个完整的二叉树&#xff0c;每个节点是一个开关&#xff0c;最初的全封闭&#xff0c;球从顶点丢弃。 每次通过开关球将将其状态反转。现在先问k球落到d当层交换机经过号。分析&#xff1a;进制编码。经过模拟几次能够看出&#xff0c;球会让开关形成连续二…

【原创】StreamInsight查询系列(六)——基本查询操作之分组聚合

上篇博文介绍了StreamInsight基础查询操作中的用户自定义聚合部分。这篇文章将主要介绍如何在StreamInsight查询中使用分组聚合。 测试数据准备 为了方便测试查询&#xff0c;我们首先准备一个静态的测试数据源&#xff1a;var weatherData new[] {new { Timestamp new DateT…

生态环境部:提升5.5亿居民饮用水环境安全保障水平

资料图&#xff1a;备用水源。于从文 摄 中新网1月30日电 据生态环境部网站消息&#xff0c;生态环境部牵头扎实推进饮用水水源地环境保护专项行动&#xff0c;成效显著。截至2018年12月31日&#xff0c;除9个问题因冬季施工难度大或实际工程量大等因素仍在整治外&#xff0c;…

8单元测试的必要性

单元测试的必要性 前言单元测试堪比汽车零件检测总结前言 积土成山,风雨兴焉。 单元测试堪比汽车零件检测 据估计,一般轿车约由1万个不可拆解的独立零部件组装而成。结构极其复杂的特制汽车,,如F1赛车等,其独立零部件的数量可达到2万个之多。可以设想下,如果汽车组装企业…

朴素高精度乘法的常数优化

2015年辽宁省赛热身赛有一道高精度乘法 传送门&#xff1a;NEUOJ 1574 A*B 1574: A * B 时间限制: 10 Sec 内存限制: 128 MB题目描述 Calculate $a \times b$. 输入 Your program will be tested on one or more test cases. In each test case, two integer $a$, $b$ ($0\le …

计算机专业今后的发展方向

计算机专业毕业后&#xff0c;大致的工作方向是软、硬、网、图 四大类&#xff0c;尤其以软件、网络为现今的首选 。从岗位上分&#xff0c;又可以分为技术道路、营销道路两大方向。 if 你选择硬件技术&#xff0c;then 从现在开始&#xff0c;牢记&#xff1a;天道酬勤&#x…

新警达尼亚尔·迪力木拉提的春运一天

新春佳节临近&#xff0c;乌鲁木齐铁路公安处民警坚守一线&#xff0c;保障旅客安全乘车。达尼亚尔迪力木拉提&#xff0c;今年26岁&#xff0c;新疆伊犁州伊宁市人&#xff0c;毕业于大连理工大学。2017年通过国家公务员考试入警为乌鲁木齐铁路公安局乌鲁木齐公安处见习民警&a…

9 单元测试中不得不知的概念

单元测试中不得不知的概念 前言软件单元及单元测试驱动函数和桩函数总结前言 做单元测试,如果不弄清楚什么是单元,那十八般武器也无的放矢了。可能在单元测试中听到最多的就是驱动函数、桩函数和逻辑覆盖,本专题就讲讲关于单元测试中那些不得不知的概念。关于逻辑覆盖,涉及…

php JSON数据格式化输出方法

php 的json_encode能把数组转换为json格式的字符串。字符串没有缩进&#xff0c;中文会转为unicode编码&#xff0c;例如\u975a\u4ed4。人阅读比较困难。现在这个方法在json_encode的基础上再进行一次美化处理。使人能方便阅读内容。 1. 使用 json_encode 输出 1 <?php2 3 …

转:C#中的abstract与virtual

C#中的abstract与virtual2008-03-14 14:01【abstract】 abstract 修饰符可以和类、方法、属性、索引器及事件一起使用。在类声明中使用 abstract 修饰符以指示类只能是其他类的基类。 抽象类具有以下特性&#xff1a; 抽象类不能实例化。 抽象类可以包含抽象方法和抽象访问器。…

从零开始单排学设计模式「UML类图」定级赛

阅读本文大概需要 3.5 分钟。本篇是设计模式系列的开篇&#xff0c;虽然之前也写过相应的文章&#xff0c;但是因为种种原因后来断掉了&#xff0c;而且发现之前写的内容也很渣&#xff0c;不够系统。所以现在打算重写&#xff0c;加上距离现在也有一段时间了&#xff0c;也算是…

10 单元测试使命

单元测试的使命前言单元测试要完成的内容总结前言 不同级别的测试的侧重点是不同的&#xff0c;单元测试也有它的使命所在。 单元测试要完成的内容 单元测试的重点主要包括验证功能的正确性、检查局部数据结构正确性、检查临界数据处理正确性、检查模块接口正确性和验证单元容…

MVVM test

示例代码 public class RegisterUserViewModel{public UserInfo userInfo { get; set; }public ICommand ClickCommand { get; set; }public RegisterUserViewModel(){userInfo new UserInfo();userInfo.Age 25;this.ClickCommand new DelegateCommand<object>(OnClic…

[SCOI2009]生日礼物

这道题很容易看出是一道单调队列题。 首先我们根据珠子的位置排序。 然后按顺序枚举一个个珠子。 如果该种珠子没有出现过标记上它的位置&#xff0c;如果出现过修改并打上当前位置。当所有珠子都出现后&#xff0c;将当前位置减去打标记位置最小的一个即为当前解。 可以证明正…

.Net(c#) 通过 Fortran 动态链接库,实现混合编程

c# 与 Fortran 混合编程解决方案主要有两种&#xff1a;1. 进程级的交互&#xff1a;在 Fortran 中编译为控制台程序&#xff0c;.Net 调用&#xff08;System.Diagnostics.Process&#xff09;&#xff0c;然后使用 Process 的 StandardOutput 属性读取控制台输出内容&#xf…

11关于集成测试

集成测试的必要性 前言集成测试集成测试模式和方法总结前言 差之毫厘,失之千里。 集成测试 单元测试的目的是确认软件单元能够满足所规定的要求,将一些单元按一定的要求合成在一起就组成了集合体。集成测试的目的是确认集合体能够正确地满足所规定的要求,集成后的各软件单…

Maven 手动添加第三方依赖包及编译打包和java命令行编译JAVA文件并使用jar命令打包...

一&#xff0c;实例:新建了一个Maven项目,在eclipse中通过 build path –> configure path….将依赖包添加到工程中后&#xff0c;eclipse不报错了。但是用Maven命令 mvn clean compile 时出错如下&#xff1a; 原因是在eclipse中添加了 exteneral jar后&#xff0c;还需要在…

Codeforces Educational round 58

Ediv2 58 随手AK.jpgD 裸的虚树&#xff0c;在这里就不写了 E 傻逼贪心&#xff1f;这个题过的比$B$都多.jpg #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #include <cstdlib> #include <queue> #includ…

VC 单文档程序 隐藏程序及任务栏图标

1 在APP类InitInstance()里 注释掉&#xff1a; m_pMainWnd->ShowWindow(SW_SHOW); 2 CMainFrame::OnCreate(LPCREATESTRUCT lpCreateStruct)里加 AfxGetApp()->m_nCmdShow SW_HIDE; 3 隐藏任务栏图标&#xff1a; ModifyStyleEx(WS_EX_APPWINDOW,WS_EX_TOOLWINDOW…

12 集成测试方法之大棒集成方法

大棒集成方法大棒集成方法总结大棒集成方法 大棒集成方法先是对每一个子模块进行测试&#xff08;单元测试阶段&#xff09;&#xff0c;然后将所有模块一次性的全部集成起来进行集成测试。如图&#xff0c;先分别对A、B、C、D、E、F、G模块进行单元测试&#xff0c;然后按照设…

phonegap+emberjs+python手机店发展,html5实现本地车类别~

商城开发项目&#xff0c;现在需要做出APP&#xff0c;无奈出场前android但不是很精通。最后选择phonegap实现app。 由于之前办理购物车分为登陆和登陆后两种情况&#xff0c;登录前必须充分利用本地存储。而基于phonegap本地存储的发展是使用Html5的localstorage功能实现。特分…

世上最伟大的十个公式,1+1=2排名第七,质能方程排名第五

英国科学期刊《物理世界》曾让读者投票评选了“最伟大的公式”&#xff0c;最终榜上有名的十个公式既有无人不知的112&#xff0c;又有著名的Emc2&#xff1b;既有简单的-圆周公式&#xff0c;又有复杂的欧拉公式…… 从什么时候起我们开始厌恶数学&#xff1f;这些东西原本如此…

20位程序员关于求职的疑问,以及我给出的参考答案

作者&#xff1a;陆小凤首发&#xff1a;公众号【程序员江湖】阅读本文大概需要 6 分钟。前几天发了一条朋友圈对于求职小伙伴们提出的问题&#xff0c;我进行了收集整理&#xff0c;统一反馈。也许这20个问题也是你们遇到的问题&#xff0c;所以趁着年前赶紧把它发出来。以下2…

14 集成测试方法之自底向上集成方法

自底向上集成方法前言自底向上集成方法前言 集成测试方法没有好坏之分&#xff0c;只有哪个更适合。 自底向上集成方法 自底向上集成方法是从调用的底层开始逐级的向上集成&#xff0c;每测试完一个族群就将其挂到上一层的模块上。这种集成方法的特点是不需要写桩函数&#x…

JavaScript Document

document:文档对象 document.getElementById();//根据ID获取元素对象 document.getElementsByTagName();//根据标签名获取元素对象数组 document.getElementsByClassName();//根据类名获取元素对象数组 document.getElementsByName();//根据名字获取元素对象数组 document.crea…