作業9 DFA最小化，語法分析初步

1.將dfa最小化：教材p65 第9題

a→ 1s|1

b→0s|0

（1）正規式：s=0(1s+1)+1(0s+0)

s=01s+01+10s+10

s=(01+10)s+01+10

s=(01+10)*01+10

s->(01 | 10)* 01 | 10

（2）nfa

（3）dfa

（4）最小化dfa

a → aa | ɛ

b → b |

bb給出句子

aaab 的一個自頂向下語法分析過程，並說明回溯產生的原因是什麼？

s->ab

s->aab

s->aaab

s->aaaab

s->aaaεb

s->aaab

a->a( ɛ |c) | baa

a->aa' | baa

b->b( ɛ |c) | abb

b->bb' | abb

c->ba | ab

c->baa' | ab

c->a(ba' | b)

c->baa | bb'

c->b(aa | b')