AnswerSheet

例1.56 (p79)

いくつかの段階を経ることで、正規表現 (ab∪a)* を NFAに変換しよう．図 1.57に示す遷移図からもわかるように，表現に対応する NFAを得るまで，最も小さな部分的表現から，より大きな部分的表現へと構成していく．一般的に，この手順が状態数の最小な NFAを作るとは限らない．この例では，8個の状態からなる NFAを与えているが，等価な NFAの中で最も小さいものはわずか 2個の状態しかもたない．読者は，それを見つけられるだろうか?

DOT言語による答案と、それを Graphvizに通して得た状態遷移図

digraph NFA {
	rankdir=LR

	/* Q:set of states */
	q1  [shape=circle]
	q2  [shape=circle]

	/* Σ:alphabet */
	// a
	// b

	/* δ:transition function */
	q1 -> q1 [label=a]
	q1 -> q2 [label=a]
	q2 -> q1 [label=b]

	/* q0:start state */
	q0  [shape=point]
	q0 -> q1

	/* F:set of accept states */
	q1 [shape=doublecircle];
}

>dot "例1.56.dot" -Tgif -o"例1.56.gif"

(状態遷移図M1,M2 略)

a. 開始状態はどれか？

M1:q1, M2:q1

b. 受理状態の集合は何か？

M1:{q2}, M2:{q1,q4}

c. 入力 aabbに対して，機械が通過する状態の列は何か？

M1:(q1,q2,q3,q1,q1), M2:(q1,q1,q1,q2,q4)

d. 機械は文字列 εを受理するか？

M1:受理しない, M2:受理する

1.1で示された機械 M1と M2の正式な記述を与えよ．

<「正式な」とあれば五個組で書くべき？>

M1

1. Q:{q1,q2,q3}
2. Σ:{a,b}

3. δ:

   	a	b
   q1	q2	q1
   q2	q3	q3
   q3	q2	q1

4. q0:q1
5. F:{q2}

M2

1. Q:{q1,q2,q3,q4}
2. Σ:{a,b}

3. δ:

   	a	b
   q1	q1	q2
   q2	q3	q4
   q3	q2	q1
   q4	q3	q4

4. q0:q1
5. F:{q2q1,q4}

DFA Mの正式な記述は ({q1,q2,q3,q4,q5},{u,d},δ,q3,{q3}) である．ただし， δが以下の表で与えられる．この機械の状態遷移図を与えよ．

	u	d
q1	q1	q2
q2	q1	q3
q3	q2	q4
q4	q3	q5
q5	q4	q5

ソースファイル (1.3.dot)

俺、図書いてない Σ(ﾟДﾟ;

以下の各々の言語は，二つの簡単な言語の積集合である．それぞれについて，まず二つの簡単な言語の DFAを構成し，次に脚注4 (54ページ)で述べた構成法を用いて連結させ，与えられた言語を認識する DFAの状態遷移図を作れ．すべてにおいて，Σ={a,b}とする．

• a. {w| wは少なくとも三つの aと，少なくとも二つの bをもつ}
• b. {w| wはちょうど二つの aと，少なくとも二つの bをもつ}
• c. {w| wは偶数個の aと，一つあるいは二つの bをもつ}
• d. {w| wは偶数個の aをもち，かつ，各々の aは少なくとも一つの bの後にくる}
• e. {w| wは aで始まり，かつ，高々一つの bをもつ}
• f. {w| wは奇数個の aをもち，かつ，bで終わる}
• g. {w| wは長さが偶数であり，かつ，奇数個の aをもつ}

a. {w| wは少なくとも三つの aと，少なくとも二つの bをもつ}

少なくとも三つの aを受理する DFA

({q1,q2,q3,q4}, {a,b}, δ, q1, {q4})

少なくとも二つの bを受理する DFA

({r1,r2,r3}, {a,b}, δ, r1, {r3})

ソースファイル(1.4.a.dot)

b. {w| wはちょうど二つの aと，少なくとも二つの bをもつ}

ちょうど二つの aを含む文字列を受理する DFA

({q1,q2,q3,q4}, {a,b}, δ, q1, {q3})

少なくとも二つの bを受理する DFA

({r1,r2,r3}, {a,b}, δ, r1, {r3})

ソースファイル(1.4.b.dot)

c. {w| wは偶数個の aと，一つあるいは二つの bをもつ}

一つか二つの bを含む文字列を受理する DFA

({q1,q2,q3,q4}, {a,b}, δ, q1, {q2,q3})

偶数個の aを受理する DFA

({r1,r2}, {a,b}, δ, r1, {r1})

ソースファイル(1.4.c.dot)

d. {w| wは偶数個の aをもち，かつ，各々の aは少なくとも一つの bの後にくる}

すべての aがひとつ以上の bのあとにくる文字列を受理する DFA

({q1,q2,q3}, {a,b}, δ, q1, {q1,q2})

偶数個の aを受理する DFA

({r1,r2}, {a,b}, δ, r1, {r1})

ソースファイル(1.4.d.dot)

e. {w| wは aで始まり，かつ，高々一つの bをもつ}

aではじまる

({q1,q2,q3}, {a,b}, δ, q1, {q2})

高々一つの b

({r1,r2,r3}, {a,b}, δ, r1, {r1,r2})

ソースファイル(1.4.e.dot)

aで始まり、0か 1つの bをもつ文字列を受理する DFA

({q1,q2,q3,q4}, {a,b}, δ, q1, {q2,q3})

ソースファイル(1.4.e2.dot, 間違えて一息に作ってしまいました)

f. {w| wは奇数個の aをもち，かつ，bで終わる}

奇数個の aをもつ文字列を受理する DFA

({q1,q2}, {a,b}, δ, q1, {q2})

bで終わる文字列を受理する DFA

({r1,r2}, {a,b}, δ, r1, {r2})

ソースファイル(1.4.f.dot)

g. {w| wは長さが偶数であり，かつ，奇数個の aをもつ}

奇数個の aをもつ文字列を受理する DFA

({q1,q2}, {a,b}, δ, q1, {q2})

長さが偶数の文字列を受理する DFA

({r1,r2}, {a,b}, δ, r1, {r1})

ソースファイル(1.4.g.dot)

1.4.d の解答について

答案と解答が食い違っていたのだが、原因は「各々の a は，少なくとも一つの b の後にくる」言語の DFAがそれぞれで違っていたから。解答にはこういう図が載っているが……

• a で始まる文字列を受理する可能性があるのでは？
• a で終わる文字列がすべて受理されないのでは？

DFAを構成し，状態遷移図を作れ，すべてにおいて，Σ={a,b}とする．(問題文 大幅に省略)

• a. {w| wは部分文字列 ab を含まない}
• b. {w| wは部分文字列 baba を含まない}
• c. {w| wは部分文字列 ab と ba のどちらも含まない}
• d. {w| wは a*b* に属さない任意の文字列}
• e. {w| wは (ab+)* に属さない任意の文字列}
• f. {w| wは a*∪b* に属さない任意の文字列}
• g. {w| wはちょうど二つの a は含まない任意の文字列}
• h. {w| wは a でもなく b でもない任意の文字列}

1.5.a {w| wは部分文字列 ab を含まない}

({q1,q2,q3}, {a,b}, δ, q1, {q1,q2})

1.5.a.dot

1.5.b {w| wは部分文字列 baba を含まない}

({q1,q2,q3,q4,q5}, {a,b}, δ, q1, {q1,q2,q3,q4})

1.5.b.dot

1.5.c {w| wは部分文字列 ab と ba のどちらも含まない}

({q1,q2,q3,q4}, {a,b}, δ, q1, {q1,q2,q3})

1.5.c.dot

1.5.d {w| wは a*b* に属さない任意の文字列}

({q1,q2,q3,q4}, {a,b}, δ, q1, {q4})

1.5.d.dot

1.5.e {w| wは (ab+)* に属さない任意の文字列}

({q1,q2,q3,q4}, {a,b}, δ, q1, {q2,q4})

1.5.e.dot

1.5.f {w| wは a*∪b* に属さない任意の文字列}

({q1,q2,q3,q4}, {a,b}, δ, q1, {q4})

1.5.f.dot

1.5.g {w| wはちょうど二つの a は含まない任意の文字列}

({q1,q2,q3,q4}, {a,b}, δ, q1, {q1,q2,q4})

1.5.g.dot

1.5.h {w| wは a でもなく b でもない任意の文字列}

({q1,q2,q3,q4}, {a,b}, δ, q1, {q1,q4})

1.5.h.dot

このページの内容はほとんどが quote_pageプラグインを利用した他ページの引用である。このプラグインの使用にはいくつかの注意が必要。->QuotePageProblem

• 2010-10-28 (木) 12:50:01 SHOSHI : 1.4 d　の回答ありがとうございました。教科書の回答はへんですよね？　最初にaが来ても受理されてしまう。
• 2010-10-29 (金) 18:35:41 SHOSHI : 1.4.d.の問題は誤訳？　本当は、 {w| wは偶数個の aをもち，かつ，(aはあってもなくてもよいが)各々の aは少なくとも一つの bが後にくる} が正しい？　原書を見ていないのでわからないが・・・。
• 2010-10-29 (金) 23:18:53 SHOSHI : 1.4.cの受理状態に誤りがあると思います。状態q3r1は受理状態ではなくq2r1とq3r1が受理状態ではないでしょうか。q3r2が受理状態ならbbaが受理されてしまいます。(aが奇数個なのでNGのはず)
• 2010-11-03 (水) 02:58:19 SHOSHI : 1.4.dの問題文(原書)はこうなっていました。　　{w|w has an even number of a's and each a is followed by at least one b}
• 2010-11-26 (金) 01:56:31 ds14050 : 1.4.cは仰るとおり、q3r2は受理状態でなく、q3r1は受理状態であるべきですね。r2とつくものが受理状態になるはずがないんですから。
• 2010-11-26 (金) 02:08:19 ds14050 : 1.4.dについて。原書まで調べて知らせてくれたことに感謝します。日本語訳では aと bがひっくり返ってしまってるんですね。正しくは「aの後に一つ以上の b」だったと。疑問が解けました。

  

    Name:
    
    Comment: