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

需积分: 9 158 浏览量更新于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

形式语言与自动机ppt

形式语言与自动机PPT

形式语言与自动机发展

形式语言与自动机课件

形式语言与自动机理论

形式语言与自动机讲义

形式语言与自动机原理

最新资源