正規表現とAutomaton の問題 5.2 - 5.7

2

ASCII code の [a-z][a-z0-9]* を Σ={a,b,c...z,0,1...,9}を使って DFA で実現してみよ。

これだと大きいので

   [d-g][d-g4-7]*

を使う。

ASCII code の [d-g][d-g4-7]* を binary の正規表現で表すとどうなるか。

Σ={0,1}を使ったこれに対応するDFAを構成せよ。

以下の正規表現に対応するNFAを計算せよ。

a (00|11)*

b (01|10)*

c (01|10)*|111

d (10|11)*

e (0|1)*010

上の正規表現に対応するDFAを計算せよ。

上のDFAの否定を与えるDFAを構成してみる。

NFAの否定を構成してみよ

NFAの否定をNFAで計算するにはどうすれば良いか?

Σ = {0,1} で

    .*1.{n}1.*

を考えよう。.{n} は n 個の任意の文字が入る。

Σ = {0,1} で NFAを構成せよ。(n=0..3)

Σ = {0,1} で DFAを構成せよ。(n=0..3)

一般的にDFAの状態数は n に対していくつになるか?