競技プログラマ向け

(1)

競技プログラマ向け形式言語理論

入門 ^稲葉

_JOI

_春合宿

^一浩

₂₀₁₂

(2)

文字列やツリーやグラフの集合

について考える分野

「形式言語理論」とは

(3)

を、どうやって表現するかについて考える分野

(4)

を、どうやって表現するかについて考える分野

今日は

文字列の集合だけ扱います

(5)

を、表現するデータ構造について考える分野

(6)

#include <set>

#include <string>

std::set<std::string>

？

(7)

文字列やツリーやグラフの無限かもしれない集合

の、有限のメモリでの表現について考える分野

(8)

 {“”, “a”, “aa”, “aaa”, “aaaa”, ...}



「長さが偶数の文字列すべて」



「回文じゃない文字列」



「円周率の

10

進表記の部分列」



・・・

文字列の無限集合の例

(9)



いくつかの表現方法の紹介



どんな操作が可能か



（コンテストっぽい）応用



（夢の広がる）応用

ここからの話題

(10)

有向グラフで表現

文字列集合を

(11)

{“a”, “ba”, “bba”, ...}

S G

a

b b

「aが奇数個」

(12)

{“”, “aa”, “ab”, “b”, “bab”, ...}

SG a

b a

b b G

a

G a

b b

「aで始まって長さ2以上、

またはbで始まってbで終わる」

(13)



辺に文字が書いてある



各頂点には

 S

という印

 G

という印

 S

と

G

両方

が付いているかも

グラフで表す文字列集合

SG a

b a

b b G

a

G a

b b

こういうグラフを、

「

S

から

G

までの経路になってる文字列すべて」

という集合を表していると考えます。

(14)



有限集合は全部書ける

 root

が

、

leaf

が

の

tree

で表現する



「特定の文字列を部分に含む文字列ぜんぶ」

 KMP

法、

Aho-Corasick

法



「

a

と

b

が交互に繰り返し出てくる文字列」



ループっぽいものはグラフでサイクルを作ると書ける



書けないものもあります。



「回文」「括弧の対応が取れてる文字列」

こんな集合が表せる

S G

(15)

2

つの流儀

: DFA

と

NFA

Deterministic

Finite Automaton

 S

が

1

つ



一つの頂点から出る、

同じ文字の辺は１本以下

Nondeterministic Finite Automaton



なんでもあり



文字無し辺も

OK

とする事も

S G

S

a a

a b

b b

“”

S G

a

a b

b

(16)

 bool contains(Automaton a, String w);



与えられた文字列を含むかの判定

 Automaton complement(Automaton a);



補集合の計算

 Automaton intersect(Automaton a, Automaton b);



共通部分の計算

 Automaton equals(Automaton a);



集合として等しい？

できる操作の、ごく一部

（だいたい思いつく物はなんでもできます）

(17)

 S

が

1

つ



一つの頂点から出る、

同じ文字の辺は１本以下

bool contains(DFA a, String w);

DFA

の場合

Node v = a.S; //S

は

1

つなので始点は

1

つに決まる

foreach(char c : w)

v = a.next(v, c); //

文字が決まれば辺も

1

つ

return v.isG();

S G

a

a b

b

(18)



少しだけ難しい



問題：

 S

から

G

まで、文字列

w

に合わせて動いてたどり着く道はあるか？

bool contains(NFA a, String w);

NFA

の場合

S G

S

a a

a b

b b

“”

(19)



解法１：

DP

 bool[

頂点数

][

文字列長

+1]

bool contains(NFA a, String w);

NFA

の場合

S1 G

S2

a a

a b

b b

“”

○

“a b b a”

S1 S2

G

(20)



解法１：

DP

 bool[

頂点数

][

文字列長

+1]

bool contains(NFA a, String w);

NFA

の場合

S1 G

S2

a a

a b

b b

“”

○

×

○

“a b b a”

S1 S2

G

(21)



解法１：

DP

 bool[

頂点数

][

文字列長

+1]

bool contains(NFA a, String w);

NFA

の場合

S1 G

S2

a a

a b

b b

“”

○ ×

× ○

○ ○

“a b b a”

S1 S2

G

(22)



解法１：

DP

 O( |edge|

・

|w| )

bool contains(NFA a, String w);

NFA

の場合

S1 G

S2

a a

a b

b b

“”

○ × ○ ○ ×

○ × ○ × ×

× ○ × × ○

○ ○ ○ ×

!!

○

!!

“a b b a”

S1 S2

G

(23)



解法２：ビット

DP



○○×○

 2

進法で

“1101”

とビットにエンコードできる

 int [

文字列長さ

+1]

bool contains(NFA a, String w);

NFA

の場合

○ × ○ ○ ×

○ × ○ × ×

× ○ × × ○

○ ○ ○ ×

!!

○

!!

“a b b a”

S1 S2

G

1101 0011 1101 1000 0011

(24)



解法

3

：ビット

DP

＆前処理

 O( 2 ^|node| + |w| )

bool contains(NFA a, String w);

NFA

の場合

○ × ○ ○ ×

○ × ○ × ×

× ○ × × ○

○ ○ ○ ×

!!

○

!!

“a b b a”

S1 S2

G

SG

1101

1101 0011 1101 1000 0011

G

0011

a

1000

b

G

0011

a a

b

・・・

(25)

 NFA

を

DFA

に変換してから処理している

 NFA

の表現力＝

DFA

の表現力



サイズは指数でふくらみますが

…

解法３のポイント

(26)

 bool contains(Automaton a, String w);



与えられた文字列を含むかの判定

 Automaton complement(Automaton a);



補集合の計算

 Automaton intersect(Automaton a, Automaton b);



共通部分の計算

 Automaton equals(Automaton a);



集合として等しい？

できる操作その他

(27)

Automaton

で表現した集合

a

と集合

b

の

共通部分

を表す

Automaton

の求め方

集合と集合の共通部分

(28)

頂点と頂点のペアを作る

1 2

a a

b

3 4

a a b

b

2,3 1,3

2,4

1,4

(29)

1 2

a a

b

3 4

a a b

b

2,3 1,3

2,4

a 1,4

1 --- a ---> 2 3 --- a ---> 4

なので

b

(30)

1 2

a a

b

3 4

a a b

b

2,3 1,3

2,4

a 1,4

b

a

(31)

両方

S

なら

S

に両方

G

なら

G

に

1 2

a a

b

3 4

a a b

b

2,3 1,3

2,4

a 1,4

b

b a

「aが奇数個」 「長さが奇数」

「aが奇数個かつ 長さが奇数」

(32)

和集合

どちらかが

G

なら

G

に

1 2

a a

b

3 4

a a b

b

2,3 1,3

2,4

a 1,4

b

b a

「aが奇数個」 「長さが奇数」

「aが奇数個または 長さが奇数」

(33)



集合の補集合

 DFA

なら

G

と

G

じゃない頂点を反転するだけ

 NFA

は

DFA

に変換してください



空集合かどうか判定

 S

から

G

に到達可能か判定するだけ



集合の包含関係

（

A ⊆ B; A

が完全に

B

に含まれているか？）



「

((B

の補集合

)

と

A

の共通部分

)

が空集合か？」と同じ



集合が等しいかどうか

 A ⊆ B && B ⊆ A

（もっと効率よく判定もできます）

(34)

1

～

N

の自然数を、それぞれ長さ

M

以下のビット列に変換して

自然数のリストを表現することにした。例えば右下の変換表を使うと

[3,1,2]

が

になる。

ところがこの変換表は困りもので、

[3,3,3]

も

になるし

[1,2,3]

も

になってしまう。

変換表を受け取って、こういう困ったこと（違うリストが

同じビット列になってしまう）が起こるかどうか判定せよ。

(N,M ≦ 50)

練習問題

: “Double Meaning”

1 → 1001 2 → 00

3 → 100

100100100

(35)

“100”

が

“1001”

の

prefix

なのが問題。

これじゃ前から読んでってどちらか区別できない

想定誤^答

for(int i=0; i<code.size(); ++i) for(int j=0; j<code.size(); ++j)

if(i!=j && code[i].is_prefix(code[j])) return BAD;

return GOOD;

1 → 1001 2 → 00

3 → 100

(36)

この変換表は一意に復元可能

撃墜例

1 → 1

2 → 10

3 → 001

(37)

解答例

（もっと効率いい解法はありそう

…

）

for(int i=0; i<code.size(); ++i) if(

「

i

から始まるリストの変換結果の集合」

と「

i

以外から始まるリストの変換結果の集合」

の共通部分が空集合ではない

) return BAD;

return GOOD;

集合を使います

(38)

1 → 1001 2 → 00

3 → 100 _S ¹ ⁰ ⁰ ¹ G

1 0 0 1

0 0

1 0 0

S

1 0 0 G

1 0 0 1

0 0

1 0 0 S 0 0

「[1,...]で始まるリストの変換結果」

「[2,...]か[3,...]で始まるリストの変換結果」

(39)



集合の補集合

 DFA

なら

G

と

G

じゃない頂点を反転するだけ

 NFA

は

DFA

に変換してください



空集合かどうか判定

 S

から

G

に到達可能か判定するだけ



集合の包含関係

（

A ⊆ B; A

が完全に

B

に含まれているか？）



「

((B

の補集合

)

と

A

の共通部分

)

が空集合か？」と同じ



集合が等しいかどうか

 A ⊆ B && B ⊆ A

（もっと効率よく判定もできます）

(40)

その他にできること：

DFA

の最小化

S G

a

b b

a

S G

a

a b

G

a b

b

実は

表してる集合は同じ！

「aが奇数個」

(41)

 O(|edge| log |node|)

でできる。



最小化するとグラフの形が一つに定まる。



集合の＝の判定が簡単



共通部分や和集合や

NFA → DFA

変換は無駄に大きい

DFA

を作ることが多いので、

小さくするのが実用上は必須。

DFA

最小化の嬉しいところ

(42)

最小化のアルゴリズム

S a G

b G

a

a b b

a

b

方針：

どんな文字列

w

についても、

「頂点

v

から

w

に沿って進んだ先が

G

」

if and only if

「頂点

u

から

w

に沿って進んだ先が

G

」なら、

v

と

u

はマージする

(43)

S a G

b G

a

a b b

a

b

「

G

な頂点」

と

「

G

じゃない頂点」

はマージできないので別グループ

(44)

S a G

b G

a

a b b

a

b



注目！

(45)

S a G

b G

a

a b b

a

b

文字

‘a’

で進んだら

に入る頂点たちとそうじゃない頂点はマージ不可能

(46)

S a G

b G

a

a b b

a

b

よって分離。

(47)

S a G

b G

a

a b b

a

b

文字

‘b’

でも

同じことを繰り返す。

分割が起きた場合は、

分かれてできたグループ

を両方（元を使用済みの場合は小さい方）を使い同様に分割を繰返す

(48)

S a G

b G

a

a b b

a

b

収束したら終了マージする。

S a G

b G

a

b

(49)



最初の分割

 0

文字で

G

と

G

じゃないところに分かれる頂点を分離



次の分割

 1

文字で

G

と

G

じゃないところに分かれる頂点を分離

 ...

というループなので、収束するまでやれば正しい



を分割に使っていればは小さい方だけ使う、というところだけ工夫

(50)



問題

 DFA a

（頂点数≦

20

）



文字列

w

（長さ≦

10

万）

 0 ≦ i

＜

k ≦ |w|

な自然数の組が

1

万個

 w[i, k)

が

DFA

の表す集合に入っているか

それぞれ判定せよ

その他にできること：

セグメント木に載せる

(51)

a b b a a b a b

3 1

4 a 2

b

b a

14 23 32 4  1

1  4 23 32 41

1  4 23 32 41 12

21 34 4  3

1  2 21 34 43

1  2

21

34

43

(52)

a b b a a b a b

3 1

4 a 2

b

b a

14 23 32 4  1

1  4 23 32 41

1  4 23 32 41 12

21 34 4  3

1  2 21 34 43

1  2 21 34 43 1  3

2  4 3  1 4  2

1  3 2  4 3  1 4  2

1  3 2  4 3  1 4  2 1  3

2  4

3  1

4  2

(53)

a b b a a b a b

3 1

4 a 2

b

b a

14 23 32 4  1

1  4 23 32 41

1  4 23 32 41 12

21 34 4  3

1  2 21 34 43

1  2 21 34 43 1  3

2  4 3  1 4  2

1  3 2  4 3  1 4  2

1  3 2  4 3  1 4  2 1  3

2  4 3  1 4  2 1  1

2  2 3  3 4  4

1  1 2  2 3  3 4  4

1  1

2  2

3  3

4  4

(54)

a b b a a b a b

3 1

4 a 2

b

b a

14 23 32 4  1

1  4 23 32 41

1  4 23 32 41 12

21 34 4  3

1  2 21 34 43

1  2 21 34 43 1  3

2  4 3  1 4  2

1  3 2  4 3  1 4  2

1  3 2  4 3  1 4  2 1  3

2  4 3  1 4  2 1  1

2  2 3  3 4  4

1  1 2  2 3  3 4  4

1  1

2  2

3  3

4  4

(55)

DFA

・

NFA

の場合、

Segment Tree

の替わりに

Factorization Forest

というテクニックで

同じ機能のものが定数高さの木でできます。

※詳しくは Web

で！

(56)

練習問題

AOJ 2017

Topcoder SRM378 Div1 Hard AOJ 1169

Topcoder TCO’09 Semifinal Medium

(57)

おまけ：形式言語理論の未解決問題

Cerný

予想

DFA

を

b

考える

a b

a

b a

a b

どの頂点にいても

baaabaaab

と歩くと

…

(58)

Cerný

予想

この

DFA

の

同期語

といいます。

b

a b

a

b a

a b baaabaaab

と歩くと

…

必ず同じ点に

着きます

(59)

Cerný

予想

b b

a a

問題：

N

頂点の

DFA

が与えられる。

最短の同期語の長さを求めよ。

存在しない場合は

-1

を返せ

NP 困難

(60)

予想：同期語が存在するなら、

長さは必ず

(N-1) ²

以下である。

Jan Cerný, 1964

≪ Cerný

予想≫

(61)

論理式で表現

文字列集合を

(62)

b_after_a(string s) :=

forall i in indices(s) if s[i]==‘a’ then

exists j in indices(s) i ≦ j and s[j]==‘b’

「aが出たら後でbも出る」

(63)

even_A(string s) :=

exists A ⊆ indices(s) forall i in indices(s)

if i in A then s[i]==‘a’

else s[i]!=‘a’

& |A| mod 2 = 0

「aが偶数個」

(64)

 and, or, not , if

～

then

 (

添え字に関する

) forall

 (

添え字に関する

) exists

 (

添え字の集合に関する

) forall

 (

添え字の集合に関する

) exists

 mod

定数で数をカウント

（詳細略）（紹介だけ）

すべて

Automaton

に変換できることが

知られています

(65)

パターンで表現

文字列集合を

(66)

Perl, Ruby, Java

等での

普通のプログラミングでよく使います。

正規表現

bab(abab)*

^{「aが奇数個」}

a(a|b)(a|b)* | b((a|b)*b)?

「aで始まって長さ2以上、

またはbで始まってbで終わる」

(67)

正規表現の使用例

(68)

hoge | fuga

 hoge

の表す集合と

fuga

の表す集合の和集合

hoge*

 hoge

の表す集合の要素を

０個以上何個でも並べた文字列の集合

hoge?

 hoge

または空文字列

正規表現

(69)

NFA

で表せます

hoge*

の例

SG a

b a

b b G

a

G a

b b

(70)

NFA

で表せます

hoge*

の例

SG a

b a

b b G

a

G a

b b

S ^“” ^G

“”

(71)

foreach(i : nodes) d[i][i] = 0;

foreach(i--c-->j : edges) d[i][j] = c;

foreach(k : nodes) foreach(i : nodes) foreach(j : nodes) d[i][j] = min(

d[i][j], d[i][k]+d[k][j]);

方針：

Warshall-Floyd

逆に、

Automaton

は

すべて正規表現で書けます

1 2

a

b

(72)

foreach(i : nodes) d[i][i] = “”;

foreach(i--c-->j : edges) d[i][j] = d[i][j] | c;

foreach(k : nodes) foreach(i : nodes) foreach(j : nodes) d[i][j] =

d[i][j] | d[i][k] d[k][k]* d[k][j];

方針：

Warshall-Floyd

逆に、

Automaton

は

すべて正規表現で書けます

1 2

a

b

(73)

さっきの「

Automaton →正規表現」変換は

*

を使いすぎる。もっと減らせないか？

 | (

和集合

), * (

繰り返し

)

の他に

& (

積集合

),

￢

(

補集合

), Φ (

空集合

)

も使う正規表現を一般正規表現という

おまけ：形式言語理論の未解決問題

Star-Height

問題

bab(abab)*

￢

((

￢

(

￢

Φa

￢

Φ)a

￢

(

￢

Φa

￢

Φ)a

￢

(

￢

Φa

￢

Φ))*)

「aが奇数個」 「aが偶数個、

じゃない」

(74)

*

のネストなしで、

Automaton

を全て一般正規表現で表せるか？

Janusz Brzozowski, 1980

≪ Star-Height

問題≫

(75)

文法で表現

文字列集合を

(76)

{“1+23/(4-5)”, “00*0+0”, ...}

EXPR ::= TERM

| TERM “+” TERM | TERM “-” TERM

**TERM ::= FACTOR “*” FACTOR | FACTOR “/” FACTOR FACTOR ::= “(“ EXPR “)”**

| “0” | “1” | ... | ”9”

「一桁の数の四則演算式」

(77)

{“”, “a”, “b”, “aa”, “aba”, ...}

PALINDROME ::= “a”

| “b”

| “”

| “a” PALINDROME “a”

| “b” PALINDROME “b”

「回文」

(78)

例）

文脈自由文法

C ^ontext F ^ree G ^rammar

PALINDROME ::= “a”

| “b”

| “”

| “a” PALINDROME “a”

| “b” PALINDROME “b”

PALIN

→ “a” PALIN “a”

→ “a” “b” PALIN “b” “a”

→ “a” “b” “a” PALIN “a” “b” “a”

→ “a” “b” “a” “” “a” “b” “a”

→ “abaaba”

^左辺

^::=

^右辺

^|

^右辺

^{| ... |}

^右辺

という規則の集まりを、

「左辺の記号を右辺のどれかに書き換え」を

繰り返したら作れる文字列の集合、と見なします。

(79)

bool contains(CFG g, string w);

P ::= “”

| “a”

| “b”

| “a” P “a”

| “b” P “b”

P ::= “”

| “a”

| “b”

| “a” Q | “b” R Q ::= P “a”

R ::= P “b”

右辺の長さが

2

以下になるように変形してから・・・

(80)

bool contains(CFG g, string w);

P ::= “”

| “a”

| “b”

| “a” Q | “b” R Q ::= P “a”

R ::= P “b”

右辺の長さが

2

以下になるように変形してから・・・

動的計画法。

O ( |g| |w| ³ )

。

bool

dp[

左辺記号

][i][k] =

“

左辺記号

”

から

w[i .. k)

が作れるか？

(81)

（オーダーの意味で）世界最速は

2012

年

3

月現在

O ( |g| ・ |w| ^2.3723 )

だそうです。

行列の掛け算と同じオーダです。

bool contains(CFG g, string w);

(82)



空集合かどうかの判定



できる（簡単）



和集合の計算



できる（簡単）



共通部分

 CFG

と

CFG

の共通部分は

CFG

では書けない！



補集合

 CFG

の補集合は

CFG

では書けない！



等しさ＝の判定、包含関係

⊆

の判定



決定不能！

ほかの集合演算は？

(83)

http://hos.ac/slides/

から引用

(84)

http://d.hatena.ne.jp/ku-ma-me/20100724/p1

Post

の対応問題ゲーム

(85)

「

2

つの

CFG

の共通部分が空か？」は決定不能

A  a ₁ A “1”

| a ₂ A “2”

...

| a _r A “r”

| “$”

B  b ₁ B “1”

| b ₂ B “2”

...

| b _r B “r”

| “$”

(86)

 CFG

と

CFG

の共通部分の空判定は決定不能

 CFG

と

CFG

の共通部分は

CFG

では書けない



空判定はできるので、

Post

の対応問題が解けちゃう

 CFG

が文字列全部を表してるかの判定は決定不能（証明略）

 CFG

の補集合は

CFG

で書けない

 CFG =? CFG

や

CFG ⊆ ? CFG

は決定不能

 CFG

と

DFA

の共通部分は計算可能

 CFG ⊆ ? DFA

は判定可能

演算はあまりサポートしない

(87)

【応用事例】

文字列検索／解析以外への

(88)



和集合や文字列結合を使って、演算結果の型を計算



集合の包含判定を使って、型キャストのチェック

文字列の「型」に使う

string<(a|b)(a|b)*> s;

s = “”; //

コンパイルエラー！

s = “c” ; //

コンパイルエラー！

string<(a|b)(a|b)(a|b)*> t = s; //

エラー！

string<(a|b)(a|b)(a|b)*> u = s+s; //OK

！

(89)

プログラムが正しい順で関数を呼ぶことの検証

File file = new File(“input.txt”);

solve(file);

void solve(File file) { int T = file.ReadInt();

solveCases(T, file);

}

void solveCases(int N, File file) { if(N == 0) file.Close();

else {String s = file.ReadLine();

// solve here...

solveCases(N-1, file); }

}

(90)

File file = new File(“input.txt”);

solve(file);

void solve(File file) { int T = file.ReadInt();

solveCases(T, file);

}

void solveCases(int N, File file) { if(N == 0) file.Close();

else {String s = file.ReadLine();

// solve here...

solveCases(N-1, file); } }

MAIN ::= “new” SOLVE

SOLVE ::= “readint” CASES

CASES ::= “close” | “readline” CASES

プログラムの挙動

(91)

File file = new File(“input.txt”);

solve(file);

void solve(File file) { int T = file.ReadInt();

solveCases(T, file);

}

void solveCases(int N, File file) { if(N == 0) file.Close();

else {String s = file.ReadLine();

// solve here...

solveCases(N-1, file); } }

MAIN ::= “new” SOLVE

SOLVE ::= “readint” CASES

CASES ::= “close” | “readline” CASES

**“new” (“readint” | “readline”)* “close”**

プログラムの挙動ファイルは

この順で操作しないとダメ！

(92)

File file = new File(“input.txt”);

solve(file);

void solve(File file) { int T = file.ReadInt();

solveCases(T, file);

}

void solveCases(int N, File file) { if(N == 0) file.Close();

else {String s = file.ReadLine();

// solve here...

solveCases(N-1, file); } }

MAIN ::= “new” SOLVE

SOLVE ::= “readint” CASES

CASES ::= “close” | “readline” CASES

**“new” (“readint” | “readline”)* “close”**

CFG ⊆ ? DFA

は

決定可能

⊆ ^?

(93)

自然数の集合を表す

(2

進数表記を下位ビットから並べた文字列として

)

SG G

0 1

0 SG

1 1 G 0

0 1 0

「２の倍数」

「３の倍数」

(94)

自然数のペアや

n

個組の集合

(n

ビットを一文字として

)

S

なんでも

0 1

G 0 1

1 1

「偶数と、3 mod 4 の数のペア」

（

16, 7

）

→ (10000, 00111)

→ “00001

11100”

(95)

Automaton

で自然数の



大小関係



足し算



固定幅ビットシフト



定数での

mod

などが定義できる

いろいろな演算

もちろん



和集合



共通部分

なども・・・

(96)

こんな集合が表現できます。幾何！

(97)

まとめ

(98)



文字列の

(

無限

)

集合の幾つかの表現方法を紹介しました



有向グラフで表現する



論理式で表現する



パターンで表現する



文法で表現する



色々な集合演算の



実装方法



応用

を紹介しました。

まとめ