形式语言与自动机：构造文法及正则表达式解析

需积分: 9 18 浏览量更新于2024-07-22 2 收藏 163KB DOC 举报

"本资源是一份关于《形式语言与自动机》的课后习题答案，由王柏和杨娟老师所编，涵盖了第二章和第三章的内容。在第二章中，涉及了如何构造右线性文法来表示长度为1至5个字符且以字母为首的字符串，以及构建上下文无关文法生成特定语言，如字符串中a的数量是b的两倍。解答详尽地展示了如何通过文法规则推导出目标语言。在第三章，主要探讨了正则集的概念和判断。例如，如何确定含有偶数个a和奇数个b的字符串集合、含有相同数量a和b的字符串集合以及不含子串aba的{a,b}*上的字符串集合是否为正则集。对于正则集的表示，给出了具体的正则式构造方法，如通过构造自动机或逻辑分析生成式之间的关系。针对两个具体的文法G1和G2，题目要求找到它们的正则式表示。在解答中，通过逐步转换和消元文法生成式，最终得出每个文法对应的正则表达式，体现了从形式语言理论到实际应用的转化过程。这份习题答案对于学习者理解和掌握形式语言与自动机的基本概念、构造方法以及正则集的识别和转换至关重要，有助于深化对理论知识的理解，并能够进行实践应用。"

(3)以 b 为首后跟若干个 a 的字符串的集合

(4) 含有两个相继 a 和两个相继 b 的由 a 和 b 组成的所有字符串集合

答：（1）右线性文法 G=({S},{a,b},P,S)

P: S→aS S→bS S→ε

(2) 右线性文法 G=({S},{a,b},P,S)

P: S→aS S→bS S→abb

(3) 此正则集为{ba*}

右线性文法 G=({S,A},{a,b},P,S)

P: S→bA A→aA A→ε

(4) 此正则集为{{a,b}*aa{a,b}*bb{a,b}*, {a,b}*bb{a,b}*aa{a,b}*}

右线性文法 G=({S,A,B,C},{a,b},P,S)

P: S→aS/bS/aaA/bbB

A→aA/bA/bbC

B→aB/bB/aaC

C→aC/bC/ε

7.设正则集为 a(ba)*

(1) 构造右线性文法

(2) 找出（1）中文法的有限自 b 动机

答：（1）右线性文法 G=({S,A},{a,b},P,S)

P: S→aA A→bS A→ε

（2）自动机如下：

(p2 是终结状态)

9.对应图（a）(b)的状态转换图写出正则式。（图略）

（1）由图可知 q

=aq

+bq

+a+ε

=aq

+bq

=aq

+bq

=>q

=abq

+bq

+aaq

+aa

=(b+ab) q

+aaq

+aa

=(b+ab) *( aaq

+aa)

=>q

=aq

+b(b+ab) *( aaq

+aa ) +a+ε

= q

(a+b (b+ab) *aa)+ b(b+ab) *aa+a+ε

=(a+b (b+ab) *aa) *((b+ab) *aa+a+ε)

=(a+b (b+ab) *aa) *

(3) q

=aq

+bq

+a+b

=aq

+bq

=aq

+bq

=>q

=aq

+baq

+bbq

+ba+b

=(ba)*(aq

+bbq

+ba+b)

=>q

=aaq

+abq

+bq

+ab+a

=(ab)*(aaq

+bq

+ ab+a)

P1 P2

剩余14页未读，继续阅读

ziguirr

粉丝: 0
资源: 1

形式语言与自动机：构造文法及正则表达式解析

北京邮电大学形式语言与自动机2020期末考试题

形式语言与自动机习题答案

形式语言与自动机理论试题答案解析.doc

bupt形式语言与自动机

形式语言与自动机理论pdf

在《形式语言与自动机入门：预备知识与课程概览》一书中，如何系统性地理解形式语言和自动机的定义及其在计算机科学中的应用？

如何通过《哈尔滨工业大学（HIT）形式语言与自动机习题》来深入理解上下文无关文法（CFG）及其在形式语言与自动机理论中的应用？

哈工大形式语言与自动机理论mooc练习题

形式语言与自动机笔记

如何根据Peter Linz的《形式语言与自动机导论：第三版》理解正规语言与正则表达式之间的关系？

最新资源