自动机理论习题解答：2.2节2.2.1(a)状态分析与转移表

5星 · 超过95%的资源需积分: 14 21 浏览量更新于2024-07-26 1 收藏 645KB DOC 举报

自动机理论、语言和计算导论是一门深入探讨有限状态机器、形式语言以及计算过程基础的课程。在课程的第2.2节中，涉及了一道关于构造一个特定类型的自动机的练习题。题目要求我们根据给定的条件设计一个有穷自动机，用于判断一个序列中大理石球是否连续两次从D槽滚出。首先，理解题目背景至关重要。自动机在这里被用来模拟一个简单的游戏规则：有三个开关，每个开关可以向左（0）或向右（1）切换，表示大理石球可能的运动方向。状态由这三者组合表示，即三个0或1的二进制序列，同时标记上之前一轮是否接受输入（通过D槽）。初始状态是000r，意味着第一个大理石球没有从D槽滚出。有16种可能的状态，但只有13种可以从初始状态出发。这些状态之间通过输入A或B进行转换，如果前一轮球没滚出D，则下一轮对应的状态不变；如果球滚出D，则某些状态会改变为接受状态（尾部添加'a'）而其他保持不变或变为拒绝状态（尾部添加'r'）。转移表中的'*'符号表示从该状态可以通过输入到达下一个状态，而普通字符则表示不接受输入时的状态转移。例如，当处于000r状态并输入A时，会切换到100或011状态，具体取决于当前的开关组合。如果球之前未滚出D（000a），则继续保持011状态，如果之前滚出D（000r），则变为100状态。这个练习不仅测试了对自动机基本概念的理解，如状态转移、状态空间和接受/拒绝状态，还锻炼了设计和应用自动机处理问题的能力。学生需要理解如何根据题目描述动态构建状态机，并确定其正确性。在解决这类问题时，关键在于仔细分析输入和状态之间的关系，以及如何根据输入规则来更新状态。这对于理解计算机科学中的抽象模型以及形式化方法非常重要。

http://www.zhiwenweb.cn/article.asp?id=122 6

利用定理 3。7 每个用正则表达式来定义的语言也可用穷自动机来定义

Exercise 3.2.6(a)

(Revised 修改 1/16/02) LL* or L

Exercise 3.2.6(b)

The set of suffixes of strings in L. (以)L 中串(作为)后缀/下标的集合。

Exercise 3.2.8

Let R

(k)

ijm

be the number of paths from state i to state j of length m that go through no

state numbered higher than k. We can compute these numbers, for all states i and j,

and for m no greater than n, by induction on k.

令 R

(k)

ijm

为从状态 i 到状态 j，长度为 m，且没有经过编号大于 k 的路径的个数。

对于所有状态 I 和 j，以及 m（m≤n），通过对 k 归纳来计算这个个数。

Basis: R

ij1

is the number of arcs (or more precisely, arc labels) from state i to state j.

ii0

= 1, and all other R

ijm

's are 0.

基础: k=0，R

ij1

是由状态 i 到状态 j 的箭弧（更准确的说，是箭弧标号）的个数。

ii0

= 1,其他的 R

ijm

's 都为 0。

Induction: R

(k)

ijm

is the sum of R

(k-1)

ijm

and the sum over all lists (p1,p2,...,pr) of

positive integers that sum to m, of R

(k-1)

ikp1

* R

(k-1)

kkp2

(k-1)

kkp3

*...* R

(k-1)

kkp(r-1)

* R

(k-1)

kjpr

Note r must be at least 2.

归纳: R

(k)

ijm

是 R

(k-1)

ijm

的和，R

(k-1)

ikp1

* R

(k-1)

kkp2

(k-1)

kkp3

*...* R

(k-1)

kkp(r-1)

* R

(k-1)

kjpr

。

(p1,p2,...,pr)是所有和为 m 的正整数序列，r 大于等于 2。

The answer is the sum of R

(k)

1jn

, where k is the number of states, 1 is the start state,

and j is any accepting state.

答案就是 R

(k)

1jn

的总和，其中 k 是状态个数，1 为开始状态，j 是任意接受状态。

Solutions for Section 3.4

Exercise 3.4.1(a)

志文工作室

http://www.zhiwenweb.cn/article.asp?id=122 6

Replace R by {a} and S by {b}. Then the left and right sides become {a} union {b} =

{b} union {a}. That is, {a,b} = {b,a}. Since order is irrelevant in sets, both languages

are the same: the language consisting of the strings a and b.

将 R 替换为{a} ，S 替换为{b}。等式变为{a} + {b} = {b} + {a}. 也就是 {a,b} =

{b,a}. 因为集合中元素的顺序是无关紧要的，所以，等式两边是一样的：由串 a

和 b 构成的语言。

Exercise 3.4.1(f)

Replace R by {a}. The right side becomes {a}*, that is, all strings of a's, including the

empty string. The left side is ({a}*)*, that is, all strings consisting of the

concatenation of strings of a's. But that is just the set of strings of a's, and is therefore

equal to the right side.

将 R 替换为{a} 。右边变为{a}*, 代表 a 组成的所有串，包含空串。左边是

({a}*)*, 代表由 a 组成的串构成的串，也就是由 a 构成的串。当然相等。

Exercise 3.4.2(a)

Not the same. Replace R by {a} and S by {b}. The left side becomes all strings of a's

and b's (mixed), while the right side consists only of strings of a's (alone) and strings

of b's (alone). A string like ab is in the language of the left side but not the right.

不等。将 R 替换为{a} ，S 替换为{b}。左边表示所有由 a 和 b（可混合）构成

的串。而右边表示只有 a 构成的串和只有 b 构成的串。像 ab 这样的串就只属于

左边的语言，而不属于右边。

Exercise 3.4.2(c)

Also not the same. Replace R by {a} and S by {b}. The right side consists of all

strings composed of zero or more occurrences of strings of the form a...ab, that is, one

or more a's ended by one b. However, every string in the language of the left side has

to end in ab. Thus, for instance, ε is in the language on the right, but not on the left.

不等。举反例，将 R 替换为{a} ，S 替换为{b}。右边表示由 0 个或多个形如

a...ab 组成的串，也就是，一个或多个 a 后面紧跟一个结尾的 b。但是，左边的

串必须以 ab 结尾。因此，ε 属于右边的语言，但不属于左边。

Solutions for Section 4.1

Exercise 4.1.1(c)

Let n be the pumping-lemma constant (note this n is unrelated to the n that is a local

志文工作室

http://www.zhiwenweb.cn/article.asp?id=122 6

variable in the definition of the language L). Pick w = 0

. Then when we write w =

xyz, we know that |xy| <= n, and therefore y consists of only 0's. Thus, xz, which must

be in L if L is regular, consists of fewer than n 0's, followed by a 1 and exactly n 0's.

That string is not in L, so we contradict the assumption that L is regular.

令 n 为泵引理常数（这个 n 与语言 L 的定义中的局部变量 n 无关）。设 w =

。把 w 打断为 w = xyz，满足|xy| <= n, 则 y 只由 0 构成。若 L 是正则的，

那么 xz 一定在 L 中。但 xz 由少于 n 个 0，后面跟着一个 1 和恰好 n 个 0 构成。

这个串不在 L 中。所以 L 不是正则语言。

Exercise 4.1.2(a)

Let n be the pumping-lemma constant and pick w = 0

, that is, n

0's. When we write

w = xyz, we know that y consists of between 1 and n 0's. Thus, xyyz has length

between n

+ 1 and n

+ n. Since the next perfect square after n

is (n+1)

= n

+ 2n +

1, we know that the length of xyyz lies strictly between the consecutive perfect

squares n

and (n+1)

. Thus, the length of xyyz cannot be a perfect square. But if the

language were regular, then xyyz would be in the language, which contradicts the

assumption that the language of strings of 0's whose length is a perfect square is a

regular language.

令 n 为泵引理常数，设 w = 0

,也就是 n

个 0。将 w 打断为 w = xyz。y 是由大

于 1 小于 n 个 0 组成的。因此 xyyz 的长度介于 n

+ 1 和 n

+ n 之间。n

的下一

个完全平方数是 (n+1)

= n

+ 2n + 1。因为 xyyz 的长度介于 n

和(n+1)

之间。

所以 xyyz 的长度不是完全平方数。若语言是正则的，那么 xyyz 也应该是正则

的。xyyz 的长度应该是完全平方数。矛盾。所以语言不是正则的。

Exercise 4.1.4(a)

We cannot pick w from the empty language. 我们无法从空集中找到 w ，因为 y

非空。

Exercise 4.1.4(b)

If the adversary picks n = 3, then we cannot pick a w of length at least n.

如果对手选择 n=3，那么我们无法找到长度至少为 n 的 w 。

Exercise 4.1.4(c)

The adversary can pick an n > 0, so we have to pick a nonempty w. Since w must

consist of pairs 00 and 11, the adversary can pick y to be one of those pairs. Then

whatever i we pick, xy

z will consist of pairs 00 and 11, and so belongs in the

志文工作室

剩余63页未读，继续阅读

majinjing3

粉丝: 2

自动机理论习题解答：2.2节2.2.1(a)状态分析与转移表

Introduction to Automata Theory, Languages, and Computation Solutions

自动机理论、语言和计算导论课后习题答案—翻译

Introduction to Automata Theory, Languages, and Computation(Second Edition)中文答案

掌握自动机理论与计算导论：课后习题完整答案解析

自动机理论与计算导论课后习题解答(中文版)

自动机理论与计算导论课后答案解析(中文版)

自动机理论、语言和计算导论课后习题答案

自动机理论、语言和计算导论课后习题答案(中文版).doc

计算复杂性导论+自动机理论、语言和计算导论课后习题答案

自动机理论、语言和计算导论课后习题答案(中文版).docx

最新资源