(10分)对于文法 G[S] :S → 1A | 0B | ε A → 0S | 1AA B → 1S | 0BB⑴ (3 分 ) 请写出三个关于 G[S] 的句子;⑵ (4 分 ) 符号串 11A0S 是否为 G [S] 的句型?试证明你的结论.⑶ (3 分 ) 试画出 001B 关于 G [S] 的语法树。
(10分)对于文法 G[S] :
S → 1A | 0B | ε A → 0S | 1AA B → 1S | 0BB
⑴ (3 分 ) 请写出三个关于 G[S] 的句子;
⑵ (4 分 ) 符号串 11A0S 是否为 G [S] 的句型?试证明你的结论.
⑶ (3 分 ) 试画出 001B 关于 G [S] 的语法树。
题目解答
答案
答:
(1) 三个 0 和 1 数量相等的串 (每个1分)
(2) S => 1A => 11AA => 11A 0S
(3)
2.(10分)设有语言 L={ α | α∈ {0,1} + ,且α不以 0 开头,但以 00 结尾 } 。
23分)试写出描述 L 的正规表达式;
⑵(7分)构造识别 L 的 DFA (要求给出详细过程,并画出构造过程中的 NFA 、 DFA 的状态转换图,以及最小DFA的状态转换图 ) 。
答:
( 1 )(3分)正规表达式: 1(0|1) * 00
( 2 )(7分)第一步(3分):将正规表达式转换为 NFA
第二步(2分):将 NFA 确定化为 DFA :(1分)
状态 输入 | I 0 | Ｉ 1 |
| ｔ | ０ | 1 |
[S] | — | ［A，D,B］ |
| q ０ | — | q 1 |
［A，D，B] | ［Ｄ,B，C］ | [D，B] | 重新命名 | q 1 | q ２ | q ３ |
[Ｄ,B，Ｃ］ | [D，Ｂ，C，Ｚ］ | ［D，B] | ｑ 2 | q 4 | ｑ ３ | |
［D，B] | [D，Ｂ，C] | [D，B] |
| q 3 | q ２ | q 3 |
［D,B，C,Z］ | ［D,B，Ｃ，Z] | [D，B］ |
| q 4 | q 4 | ｑ 3 |
DFA 的状态转换图(1分)
第三步(2分):将DFA 最小化 :(1分)
将状态划分终态与非终态两个集合:A={q0,q1,q2,q3},E={q4}
根据A、E集合的情况,对A集合进行划分
状态 输入 | Ｉ 0 | I 1 |
q0 | - | Ａ |
ｑ1 | A | Ａ |
q2 | Ｅ | Ａ |
ｑ３ | A | Ａ |
将状态集A划分为两个集合:A={q0,q1,q3},B={2}
根据A、B集合的情况,对A集合进行划分
状态 输入 | I 0 | Ｉ 1 |
ｑ0 | — | A |
ｑ１ | B | Ａ |
ｑ3 | B | A |
将状态集A划分为两个集合:A={q0},C={q1,q3}
根据A、C集合的情况,对C集合进行划分
状态 输入 | I 0 | I 1 |
ｑ１ | Ｂ | Ａ |
ｑ3 | B | A |
最小DFA 的状态转换图(1分)
