「平成24年度【春期】【秋期】 応用情報技術者 合格教本 (情報処理技術者試験)」の「形式言語」は何を言っているかさっぱりだったんですが、よく考えればあたりまえのことでした。
まず、言語とはどのように構成されているか考えて見ると、それは単純に
文字>字句>文>言語
と表せ、言語は文から成り、文は字句からなり、字句は単語から成ります。
言語を構成するには、まず文字を定義する必要があり、さらに文字から字句を構成する規則を定義する必要があります。これを字句規則と言います。
字句規則
- 文字の定義
- 文字から字句を構成する規則を定義
さらに、字句の正しい並べ方である構文規則を定義します。
構文規則
- 字句の正しい並べ方を定義(文を構成する規則を定義>
そして、字句規則と構文規則を満たす任意の文の生成法である文法を定義し言語が完成します。
例えば、「help me」、「help him」、「catch me」、「catch him」の4命令文から成る言語を考えると【ITpro:形式言語とオートマトンを学ぶ】
字句規則
- 文字はアルファベット:a~z
- 字句は「help」、「catch」、「me」、「him」
構文規則
- 命令文とは、動詞と目的語が並んだものである
- 動詞とは、help または catch である
- 目的語とは、me または him である
文法
- <命令文>→<動詞> <目的語>
- <動詞>→help | catch
- <目的語>→me | him
でこの言語は完成する。実際、この文法により「help me」、「help him」、「catch me」、「catch him」が生成でき、この文法は字句規則と構文規則に従う。