オートマトン

離散的な入力と出力を持ち、自動的に動作する機会の数学的なモデル。 内部にいくつかの状態を持ち、その状態を変化させながら動作する。

重要要素

  • 入力
  • 内部状態
  • 出力

順序機械 sequential machine

出力機能の付いた有限オートマトン

Mealy型順序機械

状態間を遷移するときに出力する

Moore型順序機械

状態に出力機能がついている

型式言語 formal language

  • 言語
    • 自然言語 natural language
      • 英語, 日本語 …
    • 人工言語 artificial language
      • C, Java, SQL, HTML, …

型式言語は自然言語を研究するために提案された言語の数学的モデル。 現在では、人工言語の数学的モデル。

型式文法 formal grammar

記号列を別の記号列に書き換える書き換え規則の集まり。

書き換え規則

A -> BC という形をした規則。 A を BC に書き換える。

オートマトンと型式言語の関係

  • オートマトン -> 言語の識別
  • 型式言語 -> 言語の生成