Mercurial > hg > Members > kono > Proof > automaton

comparison a04/lecture.ind @ 408:3d0aa205edf9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
...
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Wed, 15 Nov 2023 16:24:07 +0900
parents 6f3636fbc481
children db02b6938e04
comparison
equal deleted inserted replaced
407:c7ad8d2dc157 408:3d0aa205edf9
22 状態はAの状態とBの状態の部分集合の組になる。 22 状態はAの状態とBの状態の部分集合の組になる。
23 23
24 --(a.*f)(b.*f) を考えよう 24 --(a.*f)(b.*f) を考えよう
25 25
26 abcfbffbcdf は、この正規表現にマッチする。a.*fb.*f と書いても良い。 26 abcfbffbcdf は、この正規表現にマッチする。a.*fb.*f と書いても良い。
27
28 Perl で書けば
29
30 perl -de 0
31 DB<14> if ($x =~ /^(a.*f)(b.*f)$/) { print "$1 $2\n"; }
32
33 perl -e 'if ($x =~ /^(a.*f)(b.*f)$/) { print "$1 $2\n"; }'
34
27 35
28 a.*f は以下の状態遷移で書ける。 36 a.*f は以下の状態遷移で書ける。
29 37
30 State は a0,a1,ae,af で、ae ならば受理。 38 State は a0,a1,ae,af で、ae ならば受理。
31 39
40 δb b1 f = be 48 δb b1 f = be
41 δb b1 _ = b1 49 δb b1 _ = b1
42 δb b0 _ = bf 50 δb b0 _ = bf
43 51
44 これを使って、a.*fb.*f を受理してみる。 52 これを使って、a.*fb.*f を受理してみる。
53 <a href="../automaton-in-agda/src/nfa136.agda"> nfa136.agda </a>
45 54
46 <center><img src="fig/af-concat.svg"></center> 55 <center><img src="fig/af-concat.svg"></center>
47 56
48 受理パターンは二通りある。これを非決定性があるという。 57 受理パターンは二通りある。これを非決定性があるという。
49 58