形式言語・オートマトン・計算量

イントロ

重要語の役割をつかむ

基本情報技術者試験で扱う「形式言語・オートマトン・計算量」を、IT知識なしでも意味と使いどころから学べるように整理します。まず目的をつかみ、似た言葉や条件の違いを短く見分けます。

定義

教科書では: 「形式言語・オートマトン・計算量」は、述語論理、BNF、正規表現などを手がかりに、基本情報技術者試験で何を見分けるかを整理するテーマです。
言いかえると: はじめて学ぶときは、まず「何のための言葉か」「何と混同しやすいか」を分けます。ここでは形式言語・オートマトン・計算量の定義、代表用語、基本的な読み方、簡単な適用判断を扱い、高度な実装、詳細な規格差、長い計算問題、特定製品の操作手順へ広げすぎません。そのうえで、述語論理を単語として覚えるだけでなく、BNFとの違いを短く言える状態を目指します。

要点

言語の形、状態の変化、入力サイズに対する増え方を分けて読む。述語論理が何を説明する語かを、代表例と混同しやすい語に分けて読みます。

例

場面: 入力文字列が特定パターンに合うかを状態遷移図で追う例
順に考えると: まず述語論理が何を表すかを確認します。次にBNFとの違いを、問題文の対象・条件・順序から分けます。ここでは言語の形、状態の変化、入力サイズに対する増え方を分けて読む。この順で読むと、初見の選択肢でも中心の考え方から外れた説明を除外しやすくなります。
ここが結論: この例では、言語の形、状態の変化、入力サイズに対する増え方を分けて読むことが要点です。答えを選ぶときは、オーダー記法を実行時間そのものの秒数だと思うという読み違いを避けます。

注意

確認

Q1

形式言語・オートマトン・計算量を問題で読むとき、最も適切な見方はどれですか。

まとめ