有限オートマトン

Article View: fj.sci.informatics

Article #24

Back to fj.sci.informatics Previous Next

#24

From: suzuki
Date: Thu, 02 Sep 1999 00:00

8 lines
1178 bytes

以下の証明問題がテキストを見てもよくわからないので困っています。
どなたかご存知の方、教えてください。


 n個の入力記号列からなる有限言語L={ab,(ab)^2,...,(ab)^n}は
状態数が2n+1以下の有限オートマトンでは受理されないことを示せ。
さらに、言語L'={ab,a^2 b^2,...,a^n b^n}も状態数が2n+1以下の
有限オートマトンでは受理されないことを示せ。

Technical Details

Message-ID: <7qjh7q$ovk$1@newsgw8.odn.ne.jp>

Path: arc1-ca.pugleaf.net!unknown!not-for-mail

Show Full Headers

Complete Article Headers

X-Google-Language: Japanese,JIS
X-Google-Thread: f6edc,64e0177e52b989e1,start
X-Google-Attributes: gidf6edc,public
X-Google-Thread: f4956,64e0177e52b989e1,start
X-Google-Attributes: gidf4956,public
From: "suzuki" <suzuki114@hotmail.com>
Subject: 有限オートマトン
Date: 1999/09/02
Message-ID: <7qjh7q$ovk$1@newsgw8.odn.ne.jp>
X-Deja-AN: 519777880
Content-Transfer-Encoding: 7bit
Content-Type: text/plain; charset="iso-2022-jp"
X-MimeOLE: Produced By Microsoft MimeOLE V4.72.3110.3
X-Complaints-To: news@odn.ad.jp
X-Trace: newsgw8.odn.ne.jp 936200250 25588 210.231.88.130 (1 Sep 1999 15:37:30 GMT)
Organization: odn.ne.jp
Mime-Version: 1.0
NNTP-Posting-Date: 1 Sep 1999 15:37:30 GMT
Newsgroups: fj.sci.informatics,fj.sci.math