-title: 正規表現と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を構成せよ。

--3

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


a   (00|11)*

b   (01|10)*

c   (01|10)*|111

d   (10|11)*

e   (0|1)*010

--4

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

--5

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

--6

NFAの否定を構成してみよ

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

--7

Σ = {0,1} で 

    .*1.{n}1.*

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

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

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

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