競技プログラマ向け
形式言語理論 稲葉 一浩
入門

JOI 春合宿 2012

「形式言語理論」とは文字列やツリーやグラフの集合について考える分野

「形式言語理論」とは文字列やツリーやグラフの集合を、どうやって表現するかについて考える分野

「形式言語理論」とは今日は文字列の集合だけ扱います

文字列やツリーやグラフの集合を、どうやって表現するかについて考える分野

「形式言語理論」とは文字列やツリーやグラフの集合を、表現するデータ構造について考える分野

#include <set>#include <string>

std::set<std::string>？

「形式言語理論」とは文字列やツリーやグラフの無限かもしれない集合の、有限のメモリでの表現について考える分野

文字列の無限集合の例

 {“”, “a”, “aa”, “aaa”, “aaaa”, ...}
 「長さが偶数の文字列すべて」
「回文じゃない文字列」
 「円周率の10進表記の部分列」
 ・・・ここからの話題

いくつかの表現方法の紹介
どんな操作が可能か（コンテストっぽい）応用（夢の広がる）応用

文字列集合を有向グラフで表現

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

abSbGa「aが奇数個」

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

SGbb

GbaGaa「aで始まって長さ2以上、またはbで始まってbで終わる」

グラフで表す文字列集合
 辺に文字が書いてある 各頂点には S という印
 G という印
 S と G 両方が付いているかも

aabb

SGbbbGこういうグラフを、「SからGまでの経路になってる文字列すべて」という集合を表していると考えます。

aGaaこんな集合が表せる

 有限集合は全部書ける root が S 、leaf が G の tree で表現する 「特定の文字列を部分に含む文字列ぜんぶ」
 KMP法、 Aho-Corasick法 「aとbが交互に繰り返し出てくる文字列」
 ループっぽいものはグラフでサイクルを作ると書ける 書けないものもあります。
 「回文」 「括弧の対応が取れてる文字列」

2つの流儀: DFA と NFA
Deterministic
Finite Automaton

Nondeterministic
Finite Automaton

 Sが1つ 一つの頂点から出る、同じ文字の辺は１本以下

 なんでもあり 文字無し辺もOKとする事もb

S

aaaGb

Sbab

Gb aS“”

できる操作の、ごく一部（だいたい思いつく物はなんでもできます）

 bool contains(Automaton a, String w);
 与えられた文字列を含むかの判定

 Automaton complement(Automaton a); 補集合の計算

 Automaton intersect(Automaton a, Automaton b);
 共通部分の計算

 Automaton equals(Automaton a); 集合として等しい？

bool contains(DFA a, String w);
DFAの場合 Sが1つ 一つの頂点から出る、同じ文字の辺は１本以下

bSaaGbNode v = a.S; //Sは1つなので始点は1つに決まる
foreach(char c : w)
v = a.next(v, c); //文字が決まれば辺も1つ
return v.isG();

bool contains(NFA a, String w);
NFAの場合 少しだけ難しいa

 問題：
 S から G まで、文字列 w に合わせて動いてたどり着く
道はあるか？

Sbab

Gb aS“”bool contains(NFA a, String w);
NFAの場合 解法１ ： DP
 bool[頂点数][文字列長+1]

a“aS1S2Gbba”

S1ab○○bGb aS2“”bool contains(NFA a, String w);
NFAの場合 解法１ ： DP
 bool[頂点数][文字列長+1]

a“aS1S2○G○○×bba”

S1babGb aS2“”bool contains(NFA a, String w);
NFAの場合 解法１ ： DP
 bool[頂点数][文字列長+1]

a“abS1S2○×○××○

G○○ba”

S1babGb aS2“”bool contains(NFA a, String w);
NFAの場合 解法１ ： DP O( |edge|・|w| )a“abba”

S1
S2○×○○×○×○×××○

××

○

G○

○

○

×!!○!!

S1babGb a

S2“”bool contains(NFA a, String w);
NFAの場合 解法２ ： ビットDP
 ○○×○  2進法で “1101” とビットにエンコードできる int [文字列長さ+1]“abba”

S1
S2○×○

○×○×○

×××○

××

○

G○

○

○

×!!○!!

11010011

1101

1000 0011

bool contains(NFA a, String w);
NFAの場合・・・

 解法3 ： ビットDP ＆ 前処理a

 O( 2|node| + |w| )“abGaba”

S1S2○×○○×○×○

×××○

××○

G○○○

×!!○!!

1101

0011

1101

1000 0011

bSG

0011

1101
1000bG0011

ab・・・

解法３のポイント

 NFA を DFA に変換してから処理している

 NFA の表現力 ＝ DFA の表現力
 サイズは指数でふくらみますが…

できる操作その他

 bool contains(Automaton a, String w);
 与えられた文字列を含むかの判定

 Automaton complement(Automaton a); 補集合の計算

 Automaton intersect(Automaton a, Automaton b);
 共通部分の計算

 Automaton equals(Automaton a); 集合として等しい？

集合と集合の共通部分

Automatonで表現した
集合 a と集合 b の共通部分を表す Automatonの求め方頂点と頂点のペアを作る
ba1ab 43aba2

b1,31,42,32,4

頂点と頂点のペアを作る
ba1ab 43aba2b1 --- a ---> 23 --- a ---> 4
なので1,32,3ba1,42,4

頂点と頂点のペアを作る
ba1ab 4
3aba2

b1,3

b1,4
aa2,3 b 2,4

両方SならSに両方GならGに
ba1

a2

b
「aが奇数個」

ab 4
3ab「長さが奇数」

b1,3 a 1,4a「aが奇数個かつ2,3 b 2,4 長さが奇数」

和集合
どちらかがGならGに
ba1a2b「aが奇数個」

ab 43ab「長さが奇数」

b1,3 a 1,4a「aが奇数個または2,3 b 2,4 長さが奇数」

できる操作その他

 集合の補集合
 DFA なら G と Gじゃない頂点を反転するだけ
 NFA は DFA に変換してください 空集合かどうか判定
 S から G に到達可能か判定するだけ

 集合の包含関係 （A⊆B; A が完全にBに含まれているか？） 「((Bの補集合)と A の共通部分)が空集合か？」と同じ

 集合が等しいかどうか A⊆B && B⊆A（もっと効率よく判定もできます）

練習問題: “Double Meaning”
1～N の自然数を、それぞれ長さ M 以下のビット列に変換して自然数のリストを表現することにした。例えば右下の変換表を使うと[3,1,2] が 100100100 になる。
ところがこの変換表は困りもので、[3,3,3] も 100100100 になるし
[1,2,3] も 100100100 になってしまう。

1 → 1001
2 → 003 → 100

変換表を受け取って、こういう困ったこと（違うリストが同じビット列になってしまう）が起こるかどうか判定せよ。(N,M≦50)

想定誤答“100” が “1001” の prefix なのが問題。
これじゃ前から読んでってどちらか区別できない

1 → 1001
2 → 003 → 100

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 → 1
2 → 103 → 001

解答例（もっと効率いい解法はありそう…）

集合を使いますfor(int i=0; i<code.size(); ++i)if( 「iから始まるリストの変換結果の集合」と 「i以外から始まるリストの変換結果の集合」の共通部分が空集合ではない )return BAD;
return GOOD;

1 → 1001
2 → 003 → 10001S01010G0SS

1000

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

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

00

10

1001

できる操作その他

 集合の補集合
 DFA なら G と Gじゃない頂点を反転するだけ
 NFA は DFA に変換してください 空集合かどうか判定
 S から G に到達可能か判定するだけ

 集合の包含関係 （A⊆B; A が完全にBに含まれているか？） 「((Bの補集合)と A の共通部分)が空集合か？」と同じ

 集合が等しいかどうか A⊆B && B⊆A（もっと効率よく判定もできます）

その他にできること：DFAの最小化
aSbabGbb

実は表してる集合は同じ！

aaGbbSa「aが奇数個」

Ga

DFA最小化の嬉しいところ O(|edge| log |node|) でできる。
 最小化するとグラフの形が一つに定まる。
 集合の ＝ の判定が簡単

 共通部分や和集合やNFA→DFA変換は無駄に大きいDFAを作ることが多いので、小さくするのが実用上は必須。

最小化のアルゴリズム
aGbabS方針：

Gbaab

どんな文字列 w についても、「頂点 v から w に沿って進んだ先が G」
if and only if「頂点 u から w に沿って進んだ先が G」
なら、 v と u はマージする

最小化のアルゴリズム
aGbabSGba「G な頂点」と「G じゃない頂点」
はマージできないので別グループab最小化のアルゴリズム
aGbabS

Gbaab 注目！

最小化のアルゴリズム
aGbabS文字 ‘a’ で進んだらGbに入る頂点たちとaa

そうじゃない頂点はマージ不可能b最小化のアルゴリズム
aG

babS

Gbaab

よって分離。

最小化のアルゴリズム
aGbab
S

Gbaab

文字 ‘b’ でも同じことを繰り返す。

分割が起きた場合は、分かれてできたグループを両方（元を使用済みの場合は小さい方）を使い同様に分割を繰返す最小化のアルゴリズム
aGba

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

bS

Gbaa

GbabaSbGba

最小化のアルゴリズム

 最初の分割 0文字で G と Gじゃないところに分かれる頂点を分離 次の分割 1文字で G と Gじゃないところに分かれる頂点を分離

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

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

その他にできること：セグメント木に載せる
 問題
 DFA a （頂点数≦20）
 文字列 w （長さ≦10万） 0≦ i ＜ k ≦ |w| な自然数の組が1万個
 w[i, k) が DFA の表す集合に入っているかそれぞれ判定せよ

13baab24

14233241

12213443

12213443

14233241

1423324112213443

1423324112213443a b b a a b a b

13baab241  32  4
3  14  214233241122134431  32  43  1
4  212213443142332411  32  43  1
4  2
14233241122134431  32  43  1
4  2
1423324112213443a b b a a b a b

13baab1  12  23  34  4241  12  2
3  3
4  4

1  12  23  34  41  32  43  14  2
14233241122134431  32  43  1
4  212213443142332411  32  4
3  1
4  2
14233241122134431  3
2  43  1
4  2
1423324112213443a b b a a b a b

13baab1  12  2
3  34  4241  12  23  3
4  41  12  23  34  41  32  43  14  2
14233241122134431  32  43  14  2
12213443142332411  32  43  14  2
14233241122134431  32  4
3  14  2
1423324112213443a b b a a b a b※詳しくはWebで！

DFA・NFA の場合、Segment Tree の替わりにFactorization Forestというテクニックで同じ機能のものが定数高さの木でできます。

練習問題
AOJ 2017
AOJ 1169

Topcoder SRM378 Div1 Hard
Topcoder TCO’09 Semifinal Mediumおまけ： 形式言語理論の未解決問題
Cerný 予想
baa

DFAを考えるbaaba

どの頂点にいてもbbaaabaaabと歩くと…

Cerný 予想

baabbaaabaaabaと歩くと…
必ず同じ点に着きますaba

このDFAのb同期語といいます。

Cerný 予想

問題：
N 頂点の DFA が与えられる。
最短の同期語の長さを求めよ。
存在しない場合は -1 を返せ

NP 困難a ba b≪Cerný 予想≫

予想： 同期語が存在するなら、長さは必ず (N-1)2 以下である。
Jan Cerný, 1964

文字列集合を論理式で表現

b_after_a(string s) :=forall i in indices(s)if s[i]==‘a’ thenexists j in indices(s)i≦j and s[j]==‘b’「aが出たら後でbも出る」

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が偶数個」

（詳細略） （紹介だけ）

 and, or, not , if ～ then (添え字に関する) forall (添え字に関する) exists
 (添え字の集合に関する) forall (添え字の集合に関する) exists
 mod 定数 で数をカウント
すべて Automaton に変換できることが知られています文字列集合をパターンで表現正規表現

Perl, Ruby, Java 等での普通のプログラミングでよく使います。

b*ab*(ab*ab*)*「aが奇数個」

a(a|b)(a|b)* | b((a|b)*b)?
「aで始まって長さ2以上、またはbで始まってbで終わる」

正規表現の使用例

正規表現

hoge | fuga
 hoge の表す集合と fuga の表す集合の和集合

hoge*
 hoge の表す集合の要素を０個以上何個でも並べた文字列の集合

hoge?
 hoge または空文字列

NFA で 表せます
hoge* の例
aabb

SGbb

Gba

Gaa

NFA で 表せます
hoge* の例
aa“”

Sbb“”

SGbb

Gba

G“”

aa“”

G“”

逆に、Automaton はすべて正規表現で書けます
foreach(i : nodes)方針：d[i][i] = 0;
foreach(i--c-->j : edges) Warshall-Floydad[i][j] = c;foreach(k : nodes)b 21
foreach(i : nodes)
aforeach(j : nodes)
d[i][j] = min(bd[i][j], d[i][k]+d[k][j]);逆に、Automaton はすべて正規表現で書けます
foreach(i : nodes)方針：d[i][i] = “”;foreach(i--c-->j : edges) Warshall-Floyd
ad[i][j] = d[i][j] | c;foreach(k : nodes)b 21
foreach(i : nodes)
aforeach(j : nodes)
d[i][j] =bd[i][j] | d[i][k] d[k][k]* d[k][j];おまけ： 形式言語理論の未解決問題
Star-Height 問題さっきの「Automaton→正規表現」変換は* を使いすぎる。もっと減らせないか？
 | (和集合), * (繰り返し) の他に& (積集合), ￢(補集合), Φ (空集合) も使う正規表現を一般正規表現という

b*ab*(ab*ab*)* 「aが奇数個」「aが偶数個、じゃない」￢((￢(￢Φa￢Φ)a￢(￢Φa￢Φ)a￢(￢Φa￢Φ))*)≪Star-Height 問題≫* のネストなしで、Automatonを全て一般正規表現で表せるか？
Janusz Brzozowski, 1980

文字列集合を文法で表現{“1+2*3/(4-5)”, “0*0*0+0”, ...}

EXPR ::= TERM
| TERM “+” TERM
| TERM “-” TERMTERM ::= FACTOR “*” FACTOR| FACTOR “/” FACTOR
FACTOR ::= “(“ EXPR “)”| “0” | “1” | ... | ”9”「一桁の数の四則演算式」

{“”, “a”, “b”, “aa”, “aba”, ...}PALINDROME ::= “a”
| “b”
| “”
| “a” PALINDROME “a”| “b” PALINDROME “b”「回文」

文脈自由文法
Context Free Grammar例）

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”という規則の集まりを、「左辺の記号を右辺のどれかに書き換え」を繰り返したら作れる文字列の集合、と見なします。

bool contains(CFG g, string w);
右辺の長さが2以下になるように変形してから・・・
P ::= “”
| “a”
| “b”
| “a” P “a”| “b” P “b”

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

bool contains(CFG g, string w);
右辺の長さが2以下になるように変形してから・・・
動的計画法。O ( |g| |w|3 )。

booldp[左辺記号][i][k] =“左辺記号” から w[i .. k)が作れるか？

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

bool contains(CFG g, string w);（オーダーの意味で）世界最速は2012年3月現在

2.3723O ( |g|・|w|)
だそうです。
行列の掛け算と同じオーダです。

ほかの集合演算は？

 空集合かどうかの判定  できる（簡単） 和集合の計算  できる（簡単） 共通部分
 CFG と CFG の共通部分は CFG では書けない！

 補集合
 CFG の補集合は CFG では書けない！

 等しさ ＝ の判定、 包含関係 ⊆ の判定
 決定不能！

http://hos.ac/slides/ から引用

Postの対応問題ゲーム
http://d.hatena.ne.jp/ku-ma-me/20100724/p1

「2つのCFGの共通部分が空か？」は決定不能
A  a1 A| a2 A...
| ar A| “$”“1”“2”“r”

B  b1 B| b2 B...
| br B| “$”“1”“2”“r”

演算はあまりサポートしない CFG と CFG の共通部分の空判定は決定不能
 CFG と CFG の共通部分は CFG では書けない 空判定はできるので、Post の対応問題が解けちゃう CFG が文字列全部を表してるかの判定は決定不能 （証明略）
 CFG の補集合は CFG で書けない
 CFG =? CFG や CFG ⊆? CFG は決定不能

 CFG と DFA の共通部分は計算可能
 CFG ⊆? DFA は判定可能

文字列検索／解析以外への【応用事例】

文字列の「型」に使う

 和集合や文字列結合を使って、演算結果の型を計算
 集合の包含判定を使って、型キャストのチェック

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！

プログラムが正しい順で関数を呼ぶことの検証
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); }}プログラムが正しい順で関数を呼ぶことの検証
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” SOLVESOLVE ::= “readint” CASESCASES ::= “close” | “readline” CASES

プログラムが正しい順で関数を呼ぶことの検証
File file = new File(“input.txt”);
solve(file);
void solve(File file) {int T = file.ReadInt();
solveCases(T, file);}“new” N,(“readint”
void solveCases(intFile file) { |if(N == 0) file.Close();else {String s = file.ReadLine();// solve here...
solveCases(N-1, file); }}ファイルはこの順で操作しないとダメ！
“readline”)* “close”

プログラムの挙動

MAIN ::= “new” SOLVESOLVE ::= “readint” CASESCASES ::= “close” | “readline” CASES

プログラムが正しい順で関数を呼ぶことの検証
File file = new File(“input.txt”);
solve(file);

CFG ⊆? DFAは 決定可能“readline”)* “close”⊆void solve(File file) {int T = file.ReadInt();
solveCases(T, file);}“new” N,(“readint”
void solveCases(intFile file) { |if(N == 0) file.Close();else {String s = file.ReadLine();// solve here...
solveCases(N-1, file); }}?

MAIN ::= “new” SOLVESOLVE ::= “readint” CASESCASES ::= “close” | “readline” CASES

自然数の集合を表す(2進数表記を下位ビットから並べた文字列として)1「２の倍数」

10
SG 0G0SG01G
10「３の倍数」

自然数のペアやn個組の集合(nビットを一文字として)「偶数と、3 mod 4 の数のペア」

0101S

G11（16, 7）→ (10000, 00111)→ “00001
11100”
なんでもいろいろな演算

Automaton で自然数の 大小関係
 足し算
 固定幅ビットシフト
 定数での modなどが定義できる

もちろん
 和集合
 共通部分なども・・・こんな集合が表現できます。幾何！

まとめ

まとめ

まとめ

 文字列の(無限)集合の幾つかの表現方法を紹介しました 有向グラフで表現する
 論理式で表現する パターンで表現する
 文法で表現する 色々な集合演算の 実装方法 応用を紹介しました。

aSbab

Gb aS“”