によって帰納的に定義される文字列の集合。
狭義には、句構造文法によって定義される言語を指す。
これまで当然のように「オートマトン」と言う言葉を使ってきました。元々は自動人形、日本で言うと江戸時代に流行った「からくり人形」*1を指していました。それを計算機科学者がちゃっかりいただいて、今の状態と入力から次の状態(と出力)が決まる抽象的カラクリの名称にました。「有限」はあらかじめ有限種類の状態が決まっている型をいいます。それ以外に容量に制限のない外部記憶も状態として使える型があり、記憶の量やアクセス方法によって「線形有界オートマトン」「プッシュダウンオートマトン」などがあります。ここでは有限状態しかない有限オートマトンを扱います。前回のセルラーオートマタは有限オートマトンが並んだものです。…
大変更新に間があったお詫びは次回に述べます。実は下書きは大体できていたのでそれをまずUPします。 ネットワークアルゴリズムはひとまず中断し、これから有限オートマトンと正規表現について見ていきます。プログラミング技術的には正規表現がとても大切ですが、アニメーションの派手さ的には有限オートマトンが一押しです。有限オートマトンの考え方はすっきりしたプログラムを作る際に欠かせないものでもあります。と言うわけでまずは有限オートマトンのアニメーションを出します。 ところで正規表現と有限オートマトンは何か関係あるの、とのお言葉、大変的確なご質問です。実はどちらも文字列、記号列を指定する方法で等しい能力を持つ…
１．さまざまな文字コード（情報交換用符号） ２．自然言語を定義する形式言語 ３．逆ポーランド記法 ４．状態遷移 ５．有限オートマトン ６．AI（人工知能） 【令和５年度】 いちばんやさしい 基本情報技術者 絶対合格の教科書＋出る順問題集 作者:高橋 京介 SBクリエイティブ Amazon 情報に関する理論は多岐にわたり、さまざまな要素が組み合わさっています。 以下に、情報理論、形式言語理論、逆ポーランド記法、状態遷移、有限オートマトン、AI（人工知能）について解説します。 amprime.hatenablog.com １．さまざまな文字コード（情報交換用符号） 文字コードは、テキストデータや文…
｜形式言語の概要 ｜正規（正則）言語の概要 ｜BNF(Backus-Naur Form)記法の概要 ｜形式言語の活用法 ＜プログラミング言語設計＞ ＜コンパイラ構築＞ ＜自然言語処理（NLP）＞ ｜形式言語の使用上の注意点 ＞正確性： ＞複雑性： ＞適用範囲： ｜まとめ（形式言語） 【令和５年度】 いちばんやさしい 基本情報技術者 絶対合格の教科書＋出る順問題集 作者:高橋 京介 SBクリエイティブ Amazon ここでは、わたしが独学で学んだ「基本情報技術者試験」の試験科目「基礎理論」より、「形式言語（コンピュータの厳密な表現）」として「プログラミング言語や自然言語をコンピュータで処理するた…
www.amazon.co.jp
dlit.hatenablog.com
ja.wikipedia.org
www.trs.cm.is.nagoya-u.ac.jp
www.trs.css.i.nagoya-u.ac.jp
www.chimaira.org
www.kmonos.net
xtech.nikkei.com
kmizu.hatenablog.com
