1.将DFA最小化：教材P65 第9题
答：
|
{1,2,3,4,5} |
{6,7} |
|
{1,2} -> b -> {2} {3,4} -> b -> {6,7} {5} -> b {1,2,3,4,5}可区分，划分 |
|
|
{1,2},{3,4},{5} |
{6,7} |
|
|
{6,7} -> b -> {6,7} {6,7}不可区别，等价 |
|
{1,2} -> a -> {3,4} , {3,4} -> a , {5} -> a -> {3,4} {1,2} -> c , {3,4} -> c -> {3,4} , {5} -> c {1,2} -> d , {3,4} -> d -> { 5} , {5} -> d {1,2},{3,4},{5}不可区别，等价 |
|
DFA最小化: {1,2},{3,4},{5},{6,7}
- 构造以下文法相应的最小的DFA
S→ 0A|1B
A→ 1S|1
B→0S|0
答:
正规式：
S = 0A + 1B
= 0 ( 1S + 1 ) + 1 ( 0S + 0 )
= 01S + 01 + 10S + 10
= ( 01 + 10 )S + ( 01 + 10 )
= (01|10)*(01|10)
NFA:
DFA:
|
|
|
0 |
1 |
|
1 |
{S} = {SAD} |
{BE} |
{CF} |
|
2 |
{BE} |
|
{ADG} |
|
3 |
{CF} |
{ADG} |
|
|
4 |
{ADG} |
{BE} |
{CF} |
简化：
|
{1,2,3} |
{4} |
|
{1} -> 0 -> {1,2,3} , {2} -> 0 , {3} -> 0 -> {4} 可区别，划分 |
|
|
{1},{2},{3} |
{4} |
|
|
{4} -> 0 -> {2} {4} -> 1 -> {3} {4}不可区别，等价 |
|
{1,2,3} |
|
|
{1} -> 1 -> {3} , {2} -> 1 -> {4} , {3} -> 1 {1},{2},{3}不可区别，等价 |
|
3.给定如下文法 G[S]：
S →AB
A → aA | ɛ
B → b | bB
给出句子aaab 的一个自顶向下语法分析过程，并说明回溯产生的原因是什么？
答：
S -> AB
S -> aAB
S -> aaAB
S -> aaaAB
S -> aaaɛb
S -> aaab
回溯产生的原因：反复提取公共左因子
4.P100 练习4，反复提取公共左因子，对文法进行改写。
答:
S -> C$
C -> bA | aB
A -> aC' | bAA
B -> bC' | aBB
C' -> C | ɛ