形式语言与自动机理论试题

形式语言与自动机理论试题 一、按要求完成下列填空 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 时 ， 进 入 陷 阱 状 态 ） 1S01100,10 (2) {x|x{0， 1}+且x 的 第 十 个 字 符 为1} （ 设 置 一个 陷 阱 状 态 ， 一旦 发 现x 的 第 十 个 字 符 为0， 进 入 陷 阱 状 态 ） 1S0,10,10,10,10,110,0,10,10,10,10,1 二、判断（正确的写 T，错误的写 F） 5x2 ' 1. 设1R 和2R是 集 合 {a,b,c,d,e} 上 的 二 元 关 系 ， 则3231321)(RRRRRRR ( T ) 任取(x.,y),其中 x,y},,,,{edcba，使得321)(),(RRRyx。 )),(),((321RyzRRzxz },,,,{edcbaz )),(),(),((321RyzRzxRzxz )),(),(()),(),((3231RyzRzxzRyzRzxz 3231),(),(RRyxRRyx 3231),(RRRRyx 2.对于任一非空集合 A，ΦA2 ( T ) 3.文 法 G： S A|AS A a|b|c|d|e|f|g 是 RG ( F ) 4.3 型 语 言 2 型 语 言 1 型 语 言 0 型 语 言 ( T ) 5.s（rs+s） * r=rr * s（rr * s） * ( F ) 不 成 立 ，假 设 r,s 分 别 是表 示 语 言 R，S 的正则表 达 式 ，例 如 当 R={0}，S={1}, L(s(rs+s)*r)是以 1 开 头 的字 符 串 ，而 L(rr*s(rr*s)*)是以 0 开 头 的字 符 串 .L(s(rs+s)*r)  L(rr*s(rr*s)*) 所 以 s(rs+s)*r rr*s(rr*s)*,结 论 不 成 立 三 、设文 法 G 的产 生 式 集如 下 ，试 给 出 句 子 aaabbbccc 的至 少 两 个 不 同 的推 导 （12 分 ）。 aSBCaBCS| abaB  bB→ bb CB...