ノート:正規言語

以下に示す性質（いずれも等価） うまく言えないけど、等価とは思えない。等価ということは必要十分ということだと思うが、TMで受理するものが正規文法だけということはないと思うのだが。他にも正規表現（少なくともリンク先を考えると）と等価というのも納得がいかない。が、自分でうまく書けないので指摘にとどめる。まちがっていたらごめんなさい。

「読み取り専用」のチューリングマシンであることにご注意ください。このチューリングマシンはテープに書き込めないので通常のチューリングマシンより制限されています。また、正規表現の中の「形式言語理論における定義」と本項目での定義を比べていただければ同じであることがわかるかと思います。--Melan 2006年11月4日 (土) 01:08 (UTC)