|
37
|
1 -title: 正規表現とAutomaton の問題 5.2 - 5.7
|
|
|
2
|
|
|
3 --2
|
|
|
4
|
|
|
5 ASCII code の [a-z][a-z0-9]* を Σ={a,b,c...z,0,1...,9}を使って DFA で実現してみよ。
|
|
|
6
|
|
|
7 これだと大きいので
|
|
|
8
|
|
|
9 [d-g][d-g4-7]*
|
|
|
10
|
|
|
11 を使う。
|
|
|
12
|
|
|
13 ASCII code の [d-g][d-g4-7]* を binary の正規表現で表すとどうなるか。
|
|
|
14
|
|
|
15 Σ={0,1}を使ったこれに対応するDFAを構成せよ。
|
|
|
16
|
|
|
17 --3
|
|
|
18
|
|
|
19 以下の正規表現に対応するNFAを計算せよ。
|
|
|
20
|
|
|
21
|
|
|
22 a (00|11)*
|
|
|
23
|
|
|
24 b (01|10)*
|
|
|
25
|
|
|
26 c (01|10)*|111
|
|
|
27
|
|
|
28 d (10|11)*
|
|
|
29
|
|
|
30 e (0|1)*010
|
|
|
31
|
|
|
32 --4
|
|
|
33
|
|
|
34 上の正規表現に対応するDFAを計算せよ。
|
|
|
35
|
|
|
36 --5
|
|
|
37
|
|
|
38 上のDFAの否定を与えるDFAを構成してみる。
|
|
|
39
|
|
|
40 --6
|
|
|
41
|
|
|
42 NFAの否定を構成してみよ
|
|
|
43
|
|
|
44 NFAの否定をNFAで計算するにはどうすれば良いか?
|
|
|
45
|
|
|
46 --7
|
|
|
47
|
|
|
48 Σ = {0,1} で
|
|
|
49
|
|
|
50 .*1.{n}1.*
|
|
|
51
|
|
|
52 を考えよう。.{n} は n 個の任意の文字が入る。
|
|
|
53
|
|
|
54 Σ = {0,1} で NFAを構成せよ。(n=0..3)
|
|
|
55
|
|
|
56 Σ = {0,1} で DFAを構成せよ。(n=0..3)
|
|
|
57
|
|
|
58 一般的にDFAの状態数は n に対していくつになるか?
|
|
|
59
|
|
|
60
|
