http://metabolomics.jp/mediawiki/index.php?action=history&feed=atom&title=Aritalab%3ALecture%2FAutomata%2FPumpingLemma 2026-04-07T14:41:49Z Revision history for this page on the wiki MediaWiki 1.19.1 http://metabolomics.jp/mediawiki/index.php?title=Aritalab:Lecture/Automata/PumpingLemma&diff=254339&oldid=prev 2011-06-02T08:06:14Z

<p></p> <table class='diff diff-contentalign-left'> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr valign='top'> <td colspan='2' style="background-color: white; color:black;">← Older revision</td> <td colspan='2' style="background-color: white; color:black;">Revision as of 08:06, 2 June 2011</td> </tr><tr><td colspan="2" class="diff-lineno">Line 20:</td> <td colspan="2" class="diff-lineno">Line 20:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background: #eee; color:black; font-size: smaller;"><div># 任意の i に対し、uv&lt;sup&gt;i&lt;/sup&gt;wx&lt;sup&gt;i&lt;/sup&gt;y &amp;isin; L</div></td><td class='diff-marker'>&#160;</td><td style="background: #eee; color:black; font-size: smaller;"><div># 任意の i に対し、uv&lt;sup&gt;i&lt;/sup&gt;wx&lt;sup&gt;i&lt;/sup&gt;y &amp;isin; L</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'>&#160;</td><td style="background: #eee; color:black; font-size: smaller;"></td></tr> <tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>こちらも十分に長い文脈自由言語の導出を考え、同一の変数 X&#160; がその過程で 2 回以上現れる部分を考えます。こちらは絵を使って考えるとわかりやすく、[[Aritalab:Lecture<del class="diffchange diffchange-inline">/Basic</del>/Automata/ContextFree|文脈自由言語のページ]]で説明しています。</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>こちらも十分に長い文脈自由言語の導出を考え、同一の変数 X&#160; がその過程で 2 回以上現れる部分を考えます。こちらは絵を使って考えるとわかりやすく、[[Aritalab:Lecture/Automata/ContextFree|文脈自由言語のページ]]で説明しています。</div></td></tr> </table>

Adm http://metabolomics.jp/mediawiki/index.php?title=Aritalab:Lecture/Automata/PumpingLemma&diff=254338&oldid=prev 2011-06-01T15:25:42Z

<p>moved <a href="/mediawiki/index.php?title=Aritalab:Lecture/Basic/Automata/PumpingLemma&amp;action=edit&amp;redlink=1" class="new" title="Aritalab:Lecture/Basic/Automata/PumpingLemma (page does not exist)">Aritalab:Lecture/Basic/Automata/PumpingLemma</a> to <a href="/wiki/Aritalab:Lecture/Automata/PumpingLemma" title="Aritalab:Lecture/Automata/PumpingLemma">Aritalab:Lecture/Automata/PumpingLemma</a></p> <table class='diff diff-contentalign-left'> <tr valign='top'> <td colspan='1' style="background-color: white; color:black;">← Older revision</td> <td colspan='1' style="background-color: white; color:black;">Revision as of 15:25, 1 June 2011</td> </tr></table>

Adm http://metabolomics.jp/mediawiki/index.php?title=Aritalab:Lecture/Automata/PumpingLemma&diff=254337&oldid=prev 2010-10-30T02:01:04Z

<p>New page: == なぜ補題なのか == 正規言語・文脈自由言語において、言語が受理する列の中にある特定部分列を任意の回数繰り返した列も必ず L で受理...</p> <p><b>New page</b></p><div>== なぜ補題なのか ==<br /> 正規言語・文脈自由言語において、言語が受理する列の中にある特定部分列を任意の回数繰り返した列も必ず L で受理されることを示した定理を、ポンピング補題 (pumping lemma) と呼びます。具体的には以下の2種があります。<br /> # 正規言語におけるポンピング補題<br /> # 文脈自由言語におけるポンピング補題<br /> いずれも与えられた言語が正規言語や文脈自由言語に含まれないことを示す証明に用いられるので、補題 (lemma) と呼ばれています。<br /> またポンピング補題は言語を規定する必要条件であり、十分条件ではありません。これを満たすからといって正規言語や文脈自由言語であるとは限りません。<br /> <br /> ==　正規言語のポンピング補題 ==<br /> 有限でない正規言語 L に属する任意の列 z についてある定数 K が存在し、以下が成立します。<br /> # z = xyz<br /> # |y| &gt; 0, | xy | &amp;le; K<br /> # 任意の i に対して x y&lt;sup&gt;i&lt;/sup&gt; z &amp;isin; L<br /> <br /> 正規言語 L に対応する有限オートマトン D を考えます。L は無限集合なので必ず D の状態数より長い列を受理し、その場合、同じ状態を2回以上通ります。この状態を訪れてから再び戻ってくるまでの最短列を y とすれば、上の補題が成立します。<br /> <br /> == 文脈自由言語のポンピング補題 ==<br /> 有限でない文脈自由言語 L についてある定数 K が存在し、L に属する任意の列 z ( |z| &gt; K ) において以下が成立します。<br /> # z= uvwxy<br /> # vx &amp;ne; &amp;epsilon;<br /> # 任意の i に対し、uv&lt;sup&gt;i&lt;/sup&gt;wx&lt;sup&gt;i&lt;/sup&gt;y &amp;isin; L<br /> <br /> こちらも十分に長い文脈自由言語の導出を考え、同一の変数 X がその過程で 2 回以上現れる部分を考えます。こちらは絵を使って考えるとわかりやすく、[[Aritalab:Lecture/Basic/Automata/ContextFree|文脈自由言語のページ]]で説明しています。</div>

Adm