ポンプの補題の証明は比較的簡単ですが、言っていることの解釈や使い方は難しいです。 内容: なんかオカシイ ポンプの補題 正規言語 ポンプの補題 再度 「ポンプする」とは 「ポンプしない」とは 回文の全体は正規言語ではない おわりに なんかオカシイ インターネット上で、ポンプの補題と回文について説明しているスライドに出会いました*1。回文とは、「シンブンシ」とか「タケヤブヤケタ」のように、逆向きに読んでも同じになる文字列のことです。件のスライドは「文字列が回文か否かを、正規表現を使って判断できない」ことを示していて、結論自体は正しいのですが、途中の議論がだいぶアヤシイ(つうか間違ってます)。 でも、「しょうがないかな」という気もします。回文の全体が正規言語にならないことを示すにはポンプの補題〈pumping lemma〉を使います。このポンプの補題は、その表現が複雑で、取り扱いが難しいのです
平成18年度I-1期・I113 オートマトンと形式言語(Automata and Formal Languages)@能美キャンパス 本ページは平成18年度I-1期(4月6日〜6月2日)にJAISTの石川キャンパスで 開講されている『I113 オートマトンと形式言語(Automata and Formal Languages)』の授業のページです. 上原はI-2期に東京田町キャンパスでも同じ授業を担当しています. 田町キャンパスでの授業に関するページはこちらを御覧下さい. サポート情報 基本情報 シラバス 教場: I3・4講義室 講義時間(Lectures): 水曜日1時限(Wed;9:20〜10:50),金曜日2時限(Fri;11:00〜12:30) オフィスアワー(Office Hour): 水曜日3時限(Wed;13:30〜15:00) スタジオ撮影したビデオ(Videos take
講義ノートの目次へ 情報科学で,形式言語とオートマトンの講義ノートPDF。 コンパイラやチューリングマシンによる,機械的な言語処理を実現するための理論だ。 「正規言語」や「正規文法」といったモデル化を行なう。 ここで形式言語の処理を学ぶ前に,チューリングマシンが扱える問題の範囲を知っておくとよい。 計算量理論(チューリングマシンの計算複雑性・計算可能性)のノート 形式言語を学んだら,自然言語の処理へとステップアップしよう。 自然言語処理(形態素解析や文脈自由文法)のノート 形式言語とオートマトンの講義ノートPDF しっかり学べるPDF: 数理情報科学シリーズ24 「オートマトンと形式言語の基礎」 http://p-www.iwate-pu.ac.jp/~k-yamada... 76ページ。岩手県立大の「2013後期 計算モデル論」の講義資料。 引用: 「有限オートマトンは…1940年代に神
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く