第 2 回 正規表現、非決定性オートマトン

本日の内容

• 2-1. 正規文法
• 2-2. 非決定性オートマトン

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

2-1. 正規文法

はじめに、入力データの意味や内容を解析するために、文法理論を学びます。 参考書を選ぶ時は、「コンパイラ論」のようなものが参考になります。

言語と文法

コンピュータで文字(記号)列を解釈するには、その文字列がどのようなルール で作られているかを知る必要があります。 文字列のルールを文法と言います。 そして、ルールに適合する文字列すべての集合を言語と言います。 なお、ルールから適合する文字列を導くことを生成すると言います。 特定の文法を記号 G で表す時、その文法で生成される言語を L(G) と書くこ とがあります。 なお、記号の全体集合をアルファベット と言います。 しばしばアルファベットはΣで表されます。 そして、そのアルファベットΣから作られる記号列全体の集合を ${\Sigma }^{*}$ で表します。 なお長さが0の記号列(空列)をεで表します。

アルファベット Σ

使用する記号の集合

${\Sigma }^{*}$

空列を含む生成可能な記号列すべての集合

文法 G

記号列を生成するルール

言語 L(G)

G にしたがって生成される記号列すべての集合

例2-1

正規表現

正規表現を次のように定義します。

1. ε は正規表現です。
2. アルファベット一文字は正規表現です。
3. R と S が正規表現なら、 R | S, RS, {R} は正規表現です({R} は R の 0 回以上の繰返し)。

正規表現は一つの文法になりうるので、正規表現で一つの言語を定義すること ができます。

例2-2

$G_1=\left\{\text{a}\right\}$

$L\left(G_1\right)=\left\{\text{ε},\text{a},\text{aa},\text{aaa},...\right\}$

$G_2=\text{a}\left|\text{b}\right|\text{c}$

$L\left(G_2\right)=\left\{\text{a},\text{b},\text{c}\right\}$

$G_3=\left(\text{1}|\text{2}|\text{3}|\text{4}|\text{5}|\text{6}|\text{7}|\text{8}|\text{9}\right)\left\{\left(\text{0}|\text{1}|\text{2}|\text{3}|\text{4}|\text{5}|\text{6}|\text{7}|\text{8}|\text{9}\right)\right\}$

$L\left(G_3\right)=\text{自然数}$

メモリーが有限個しか使えないコンピュータが計算できる言語は正規表現だけ であることが知られています。 このように正規表現はプログラムと非常に密接な関係にありますので、さまざ まなところで使用されています。 例えば、 MS-DOS プロンプトやコマンドプロンプトなどでも、ファイル名を指示 する時、不完全ながらも正規表現が使えます。

1. 文字は正規表現
2. 正規表現の連結は正規表現
3. ? は任意の一文字、* は任意の文字列を表します。

但し、これは ab, abab, ababab, ... などの文字列の繰り返しの表現を指定できな いので、完全な意味での正規表現ではありません。 しかし、一応複数のファイル名などを一つの文法で表すことが できます。

演習2-1

コマンドプロンプトまたは MS-DOS プロンプトで c:\windows または c:\winnt ディレクトリの中のファイルのうち、次の条件に当てはまるファイ ル名を dir コマンドを使って表示しなさい。 但し、 Windows や MS-DOS はファイル名を二つの文字列を.(ピリオド)でつな がった形で表しています。 後ろの文字列を拡張子と言います。 例えば「拡張子が txt のファイル名」は dir *.txt で表示します。

1. a で始まるファイル名
2. 拡張子が exe のファイル名
3. ファイル名の前の部分が d で終るファイル名

 java.util.regex.Pattern p = java.util.regex.Pattern.compile("a*b");
 java.util.regex.Matcher m = p.matcher("aaaaab");
 boolean b = m.matches();

 boolean b = "aaaaab".matches("a*b");

import re

p = re.compile("a*b");
print(p.search("baaaaab") != None)
print(p.match("baaaaab") != None)
if p.match("c"):
    print(True)
else:
    print(False)
for i in p.finditer("baaaaab"):
    print(i.group())

m = re.search(正規表現,文字列)

演習2-2

以下を使って、ランダムな 1000 個の文字列のうち、次の文字列 がいくつ出て来るか調べなさい。但し、文字列の長さは 5 とします。

1. a で始まる文字列
2. a を含む文字列
3. 英字で始まり、残りは英字と数字だけの文字列

演習2-3

次の正規表現が受理する言語(文字列の集合)を求めなさい。

1. a*
2. [abc]
3. <[^>]*>
4. [1-9][0-9]*

演習2-4

次の文字列を表す正規表現を示しなさい。

1. 先頭が a で始まる文字列
2. 最後が b で終る文字列
3. c を含む文字列
4. abc を含む文字列
5. abc または def を含む文字列
6. 先頭が英字または_(アンダースコア)、二文字目以降がある場合英字、数 字、または_(アンダースコア)である文字列(C 言語では名前はこ のルールに従う必要がある)

import java.util.regex.*;
class Sample {
  public static void main(String[] args){
    final String sample="This is a pen.";
    final Pattern p = Pattern.compile("\\p{Alpha}\\p{Alnum}*");
    final Matcher m = p.matcher(sample);
    while(m.find()){
      System.out.println(m.group());
    }
  }
}

import re
sample="This is a pen."
p = re.compile("[A-Za-z][A-Za-z0-9]*")
m = p.finditer(sample)
for i in m:
    print(i.group())

演習2-5

2-2. 非決定性オートマトン

ここまでは正規表現を解釈するツールを利用してきました。 これからは、原理を学ぶために正規表現をプログラムに変換する手法を学びます。 単純な正規表現ならわざわざツールに頼らなくとも簡単なプログラムで解釈で きます。

始めにオートマトンについて学びます。 オートマトンとは次のような有向グラフです。

1. 開始ノードというノードが一つ指定される
2. 終了ノードが一つ以上指定される
3. 各辺には文字が一つ以上割り振られている。

文字列に対して、開始ノードから一文字ずつたどって終了ノードにたどり着け た時、オートマトンはその文字列を受理すると言います。 一方、辺がなかったり、文字列が終った時に終了ノードではなかった時 拒否すると言います。 オートマトンにより、受理する文字列の集合が決定できます。受理する文字列 の集合をそのオートマトンが受理する言語と言います。

各ノードから出る辺に割り当てられている文字がすべて異なるオートマトンを 決定性オートマトンと言います。 このオートマトンは状態遷移図とも呼びます。 決定性オートマトンは入力により流れが分岐するだけですので、簡単にプログ ラムに変換できます。

一方、各ノードから出る辺に割り当てられている文字にダブりがあったり、 ε(空文字)が割り当てられているオートマトンを非決定性オート マトン と言います。 これから、この講義で非決定性オートマトンの受理する言語と正規文法で定められる言語が 一致することを示します。 具体的には正規文法から非決定 性オートマトンへの変換の仕方、次回の講義では非決定性オートマトンから決 定性オートマトンへの変換法を示します。 (非決定性オートマトンから正規文法への変換方法は省略します)

正規文法から非決定性オートマトンへ

帰納法により証明します。

ε を受理する非決定性オートマトンは次の通りである。

文字 A を受理するオートマトンは次の通りである。

R と S が正規表現であり、それを受理する非決定性オートマトンが存在 する時、R|S を受理する非決定性オートマトンは次の通りである。

R と S が正規表現であり、それを受理する非決定性オートマトンが存在 する時、RS を受理する非決定性オートマトンは次の通りである。

R が正規表現であり、それを受理する非決定性オートマトンが存在 する時、{R} を受理する非決定性オートマトンは次の通りである。

(証明終)

例2-3

1. 正規表現 a は次のような非決定性オートマトンになります。

   

2. 正規表現 ab は次のような非決定性オートマトンになります。

   

   但し、このオートマトンでεを考える必要は無いので、省略できます。 このように状態数の少ない等価なオートマトンを導くことを 簡単化と言います。

   

3. 正規表現 (ab|ac) は次のような非決定性オートマトンになります。

   

   但し、これも最初の入力はどちらも a なので εを考える必要はありません。 また、次の入力 b, c でともに受理状態に入ればいいので、こちらも省略できます。 そのため次のように簡単化できます。

   

4. 正規表現 (ab|ac)* は次のような非決定性オートマトンになります。

   

   これもこのように簡単化できます。

   

演習2-6

次の正規表現を受理する非決定性オートマトンを作りなさい。

1. a*
2. [abc]
3. (abc|asd)
4. .*(a|b)?
5. 1[01]*