Formal Language

CYK法

所属判定問題 CYK法 ・Gを文脈自由文法とする。入力としてw∈T^*が与えられたとき、w∈L(G)であるかどうかを判定するアルゴリズムがある。 証明: Gについて、A⇒^*εとなるような生成規則を取り除いていけばε∈L(G)かどうかを判定できる。さらにεがあるなら、L(G…

正則表現のメモ

正則表現(正規表現に同じだけど、形式言語においては正則表現と呼んで、実際にプログラミングで使うようなのは正規表現と呼んだりしている)の等式における性質がわかりづらかったので解釈をメモ。以下、正則表現r,sが集合L(r),L(s)を表すとする。記号の定義…

正則言語のPumping Lemma

正則言語のPumping Lemma ・L⊆Σ*を正則言語とする。このとき、ある定数N>=1が存在して、Lに属する長さがN以上の任意の記号列xに対して、xの分解x=uvwで次の条件を満たすものがある。 1. 1=NとなるLの記号列xについて、xはMによって受理されるので、xのMによ…