言語処理超入門 の編集履歴

tt が 2020-06-07 21:49 に編集

--- Ver.1	2017-10-15 18:53:39+09:00
+++ Ver.2	2020-06-07 21:49:45+09:00
@@ -623,7 +623,7 @@
 
 FAには非決定性有限オートマトンと決定性有限オートマトンの二種類があり、それぞれNFA(ぬふぁ)、DFA(どぅふぁ)と呼ばれている。
 
-NFAは、ある状態で特定の入力があったとき、遷移先の状態が1つに限定されないFAのことである。例えば正規式 “a*b*a” に対して “a” を入力したときのことを考えてみる。これだけでは式の最初の “a*” の一部なのか、それとも “a*b*” が実は空で、最後の “a” なのか、決定できない。次の入力が “b” であれば、前者でしかありえないし、入力がこれで終わりであれば、後者に決まる。NFAの非決定性と言う言葉はこのような事情を表現している。
+NFAは、ある状態で特定の入力があったとき、遷移先の状態が1つに限定されないFAのことである。例えば正規式 “a\*b\*a” に対して “a” を入力したときのことを考えてみる。これだけでは式の最初の “a*” の一部なのか、それとも “a\*b\*” が実は空で、最後の “a” なのか、決定できない。次の入力が “b” であれば、前者でしかありえないし、入力がこれで終わりであれば、後者に決まる。NFAの非決定性と言う言葉はこのような事情を表現している。
 
 これに対してDFAは、ある状態である入力があったとき、遷移先の状態が1つに確定するタイプのFAである。
 
@@ -638,7 +638,7 @@
 ![image003.png](/rambo/static/images/a48760c6-4666-426a-91cc-082a7e470433.png)
 
 
-一見、このような簡潔なルールで問題ないように思えるが、穴がある。例えばa|b*を、必要最小限のε遷移で考えてみると、以下のようなNFAとなる。
+一見、このような簡潔なルールで問題ないように思えるが、穴がある。例えばa|b\*を、必要最小限のε遷移で考えてみると、以下のようなNFAとなる。
 
 
 ![image004.png](/rambo/static/images/86b0ef8c-ebf7-4e2b-8cd5-ac3d87278ace.png)
@@ -1645,7 +1645,7 @@
 
 fgrepは、正規表現が扱えない代わりに、任意個の文字列を一度に検索すると言うちょっと変わったツールである。こちらは、伝統的にDFAによる実装となっている。(GNUのは少し違ったような気もする。)このfgrepに使われているアルゴリズムは、とても美しいので一度紹介したいと思っているが、今回は割愛する。その代わり、伝統的なregexの実装の雰囲気を味わうためにワイルドカードのマッチングアルゴリズムを紹介する。
 
-例として、パターン “A*BC” と文字列 “ABABC” の照合を考える。まずは先頭文字同士。
+例として、パターン “A\*BC” と文字列 “ABABC” の照合を考える。まずは先頭文字同士。
 
 ```
 A*BC    ABABC
@@ -1657,13 +1657,13 @@
 A|*BC   A|BABC
 ```
 
-パターンの方は次は “*” で、文字列には4文字残っているため、“*” とマッチさせるべき文字数は0~4のいずれかとなる。0から試してみる。
+パターンの方は次は “\*” で、文字列には4文字残っているため、“\*” とマッチさせるべき文字数は0~4のいずれかとなる。0から試してみる。
 
 ```
 A*|BC   A|BABC
 ```
 
-これだと最初の文字 “B” は一致するが、それ以降が一致しないため失敗である。次に “*” に1文字マッチさせて試してみる。
+これだと最初の文字 “B” は一致するが、それ以降が一致しないため失敗である。次に “\*” に1文字マッチさせて試してみる。
 
 ```
 A*|BC   AB|ABC
@@ -1675,11 +1675,11 @@
 A*|BC   ABA|BC
 ```
 
-ようやく、“*” 以降のすべての文字がマッチする。
-
-ここで、 “*” がいくつか含まれている場合、マッチの仕方が複数個存在することがある。例えば “*A*” と “BABAB” のマッチングを考えると、最初の “*” に “B” を対応させても、 “BAB” を対応させてもマッチは成功する。上記の方法の場合、文字数の少ない方から試行するため、“B” にマッチすることになる。一般的にはこれは逆の方が好ましいのであるが、ワイルドカードの場合、マッチするかしないかの判定のみを目的としているため、気にしても仕方がない。
-
-“*” に出会うたびにマッチさせる文字数を変化させながら、後続のマッチングを試行すると考えると、自然と再帰アルゴリズムとなる。これを素直に書き下すと、以下のようになる。
+ようやく、“\*” 以降のすべての文字がマッチする。
+
+ここで、 “\*” がいくつか含まれている場合、マッチの仕方が複数個存在することがある。例えば “\*A\*” と “BABAB” のマッチングを考えると、最初の “\*” に “B” を対応させても、 “BAB” を対応させてもマッチは成功する。上記の方法の場合、文字数の少ない方から試行するため、“B” にマッチすることになる。一般的にはこれは逆の方が好ましいのであるが、ワイルドカードの場合、マッチするかしないかの判定のみを目的としているため、気にしても仕方がない。
+
+“\*” に出会うたびにマッチさせる文字数を変化させながら、後続のマッチングを試行すると考えると、自然と再帰アルゴリズムとなる。これを素直に書き下すと、以下のようになる。
 
 ```
 matches(pat[p..], str[s..]) ::=
@@ -1695,7 +1695,7 @@
      matches(pat[p+1..], str[s..]) != SUCCESS ⇒ str[s..].length != 0 ⇒ matches(pat[p..], str[s+1..])
 ```
 
-※煩雑になるので、“*” 以外のメタ文字は無視して記述している。
+※煩雑になるので、“\*” 以外のメタ文字は無視して記述している。
 
 ループで済むところはループに直してJavaのプログラムにすると、
 
@@ -1733,7 +1733,7 @@
 }
 ```
 
-メタ文字として、“*” と “?” しか考慮していないが、文字クラスやエスケープ文字などの対応は簡単であるため、言及しない。
+メタ文字として、“\*” と “?” しか考慮していないが、文字クラスやエスケープ文字などの対応は簡単であるため、言及しない。
 
 一見、試行とバックトラックが必須であるように見えるワイルドカードの処理であるが、実はそれは必須ではなく、注意深く考えると再帰を完全に削除することも可能である。
 
@@ -1795,7 +1795,7 @@
 }
 ```
 
-“*” が複数個現れる場合、最後の “*” だけを考えれば十分と言うことに気付けば、このアルゴリズムにたどり着く。すなわち、必要なスタックは1段のみであるため、上のプログラムではそれをp0、s0と言う単純変数で済ませている。
+“\*” が複数個現れる場合、最後の “\*” だけを考えれば十分と言うことに気付けば、このアルゴリズムにたどり着く。すなわち、必要なスタックは1段のみであるため、上のプログラムではそれをp0、s0と言う単純変数で済ませている。
 
 ## 構文解析
 

tt が 2017-10-15 11:08 に投稿