1.将DFA最小化：教材P65 第9题
如下图所示DFA最小化:
DFA简化后如图：
2.构造以下文法相应的最小的DFA
S→ 0A|1B
A→ 1S|1
B→0S|0
正规文法：
S → 0(1S | 1)|1(0S | 0)
→(01S | 01)|(10S | 10)
→(01 | 10)*(01 | 10)
非确定有穷自动机NFA :
状态转换矩阵：
|
|
|
0 |
1 |
|
X |
∑{A}={ABC} |
∑{DF} = {DF} |
∑{EH}={EH} |
|
Y |
∑{DF}={DF} |
- |
∑{BI}={BCI} |
|
M |
∑{EH}={EH} |
∑{BI}={BCI} |
- |
|
N |
∑{BCI}={BCI} |
∑{DF}={DF} |
∑{EH}={EH} |
转换后DFA初态：
DFA简化：
|
I |
{X,Y,M} |
{N} |
|
{X}1={X,Y,M} {Y}1={N} {M}1={} {X} {Y} {M}可区分,划分 |
||
|
II |
{X} {Y} {M} |
{N} |
简化后的自动机DFA：
3.自上而下语法分析，回溯产生的原因是什么？
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 -> a|aC | bAA
B -> b|bC | aBB
答：
S -> C$
C -> bA | aB
A -> aC' | bAA
B -> bC' | aBB
C' -> C | ɛ