.

word 范文 形式语言与自动机理论试题答案解析

一、按要求完成下列填空

1. 给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集 （2x4'）

(1) {Φ,{Φ},{{Φ}},{Φ,{Φ}}}

(2) {Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}}

2. 设∑={0,1},请给出∑上的下列语言的文法 （2x5'）

(1)所有包含子串01011的串

S →X01011Y

X →ε|0X|1X

Y →ε|0Y|1Y

(2)所有既没有一对连续的0，也没有一对连续的1的串 A →ε|A ’|A ”

A ’ →0|01|01A ’

A ” →1|10|10A ”

3. 构造识别下列语言的DFA 2x6'

(1) {x|x ∈{0，1}+且x 以0开头以1结尾}

（设置陷阱状态，当第一个字符为1时，进入陷阱状态）

1

S 01

1

00,10

(2) {x|x ∈{0，1}+且x 的第十个字符为1}

（设置一个陷阱状态，一旦发现x 的第十个字符为0，进入陷阱状态）