计算理论计算理论5章文法与语言1

VIP免费

2025-01-13 0 0 998.5KB 75 页 5.9玖币

侵权投诉

计算理论

第五章自动机与语言

求解问题与识别语言

问题抽象为符号串的集合；

符号串称为句子，问题是句子的集合；

求解问题抽象为识别语言。

问题提出 : 如何构造可以接受及产生一个语言

的计算模型 ?

解决问题 : 对一个已经存在的字符串集合 , 如

何判断它就是符合条件的语言 ? 语言识别器。

怎样产生一个语言？如何识别这个语言？

文法

语言的产生与识别方法

文法能清晰描述语言的语法构成

文法能自动构造有效的语言识别器

文法

文法 G定义为四元组 (V,T,S,P) ，其中

V 是有限的非终极符集合；

T 是有限的终极符集合；

S 是开始符， SV。必须在某个产生式的左边出现一次；

P 是产生式的集合，且具有下面的形式：

  ，其中， (V  T )*

语言 L(G)={w| S * w}

：字符串中用产生式的右部替换左部的出现

乔姆斯基分类

文法分类：

A,BV，aT。对文法中的产生式→：

O型文法 : 短语文法。中至少含一个非终极符。

1型文法 : 上下文有关文法。它是 0型文法的特例，

要求 ||||(S→例外， S不得出现于产生式右

部)。

2型文法 : 上下文无关文法。它是 1型文法的特例，

要求产生式左部是一个非终极符 : A→ 。

3型文法 : 正则文法。它是 2型文法的特例，要求

产生式具有下面形式之一 : A→a ，A→aB 。

正则文法

上下文无关文法

上下文有关文法

短语文法

例

正则文法 G：

S aA, A  aA, A bB,

B  bB A b, B b

L = {ambn | m,n>0}

上下文无关文法 G:

S  aSb, S ab

L = {anbn | n>0}

例

上下文有关文法 G：

S  aSBC, S  aBC, CB  BC ，

aB  ab, bB bb, bC bc, cC cc

L = {anbncn | n>0}

例：某语言有文法 G：＜字母＞＜数学

＞＜标识符＞，尖括号指非终极符。终

极符 T：｛ 0, 1, 2, …, 9, a, b, …, z, A, B,

…, Z ｝。 P中的产生式有：

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

5.9 玖币 0人已下载

立即下载 VIP免费下载

摘要：

计算理论第五章自动机与语言求解问题与识别语言问题抽象为符号串的集合；符号串称为句子，问题是句子的集合；求解问题抽象为识别语言。问题提出:如何构造可以接受及产生一个语言的计算模型?解决问题:对一个已经存在的字符串集合,如何判断它就是符合条件的语言?语言识别器。怎样产生一个语言？如何识别这个语言？文法语言的产生与识别方法文法能清晰描述语言的语法构成文法能自动构造有效的语言识别器文法文法G定义为四元组(V,T,S,P)，其中V是有限的非终极符集合；T是有限的终极符集合；S是开始符，SV。必须在某个产生式的左边出现一次；P是产生式的集合，且具有下面的形式：，其中，(...

展开>> 收起<<

计算理论计算理论5章文法与语言1.pptx

共75页,预览15页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

计算理论计算理论5章文法与语言1

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择:

计算理论计算理论5章 文法与语言1

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择:

计算理论计算理论5章文法与语言1