2010-06-12から1日間の記事一覧
言語Lに関して、ξがstrong postfix (suffix) ⇔ α∈L かつ αξ ∈L となるαがある 言語Lに関して、ηがstrong prefix ⇔ α∈L かつ ηα ∈L となるαがある strong postfixの先頭文字はfollowLast集合に入る。 strong prefixの末尾文字はleadFirst集合に入る。 終状態p…
オートマトンの連接問題は「S型オートマトンとT型オートマトン」を考えるとケリが付く。Sはsubexpression、Tはtotal expressionから。S型オートマトンアルファベットA上のS型オートマトンとは、無音記号(εと同じ)を#として、A∪{#}で辺ラベル付けされた有向…
正規表現の部分式に対応するオートマトンと完全な構文単位に対応するオートマトンを区別する必要があるのだった。最初に、終状態ノードとゴールノードを区別することからはじめる。終状態はそこで終端記号が入力すると受理が成功するような状態のこと。これ…