ECMAScript(JavaScript) Ruby Python Java Go HTML Shell Script 人間がコンピュータに理解してもらうために、例外のない言語である形式言語を定義する。字句(Token)となり、それが集まって文を構成、文の集まりが言語を構成する。言語プロセッサでは、これをバラして解析する。オートマトンや文脈自由文法を用いて形式言語を分解して機械語に翻訳する。
文脈自由文法
$$ a \to b $$ という関係にあるとき、aが一つの非終端記号になるもの。
終端記号
左辺の<主語>は、右辺にある語で置き換えることができる。 右辺にあるこれらの語は、それ以上何かに置き換えることはできない。
- 非終端記号N←まだ(参照が)終わりじゃない語←まだ置き換えられる語
- 終端記号T←もう(参照が)終わりの語←もう置き換えられない語
- 生成規則P何を何で置き換えるかというルール
- 開始記号S最初に置き換える記号の指定
$$ G={N,T,P,S} $$ $$ N={非終端記号の集合}\ $$ $$ T={終端記号の集合}\ $$ $$ P={生成記号の一覧}\ $$
非終端記号
正規言語 文脈依存言語 句構造げんご(無制限言語) 文脈自由文法以外の形式言語には、以下のようなものがあります:
正規言語
正規言語は、形式言語理論におけるChomsky階層の中で最も単純な言語クラスです[3]。正規言語は以下の特徴を持ちます:
- 有限オートマトンで認識できる
- 正規表現で表現できる
- 正則文法（正規文法）で生成できる
正規言語は、文脈自由言語の真部分集合となっています。
文脈依存言語
文脈依存言語は、文脈自由言語よりも表現力が高い言語クラスです[3]。主な特徴は:
- 文脈依存文法（CSG: Context-Sensitive Grammar）で生成される
- 線形有界オートマトンで認識できる
- εを生成しない（空文字列を含まない）
文脈依存文法の生成規則は以下の形式を持ちます:
αAβ → αγβ (α, β, γ ∈ (N ∪ Σ)*, γ ≠ ε, A ∈ N)[3]
句構造言語（無制限言語）
句構造言語は、Chomsky階層の中で最も表現力が高い言語クラスです[3]。特徴として:
- 句構造文法（無制限文法）で生成される
- チューリングマシンで認識できる
- あらゆる再帰的可算言語を含む
句構造文法の生成規則は、α → β の形式を持ち、αは少なくとも1つの非終端記号を含みます[3]。
これらの言語クラスは、以下の包含関係を持っています:
正規言語 ⊂ 文脈自由言語 ⊂ 文脈依存言語 ⊂ 句構造言語
この階層構造は、Chomsky階層として知られており、各言語クラスの表現力と計算複雑性を表しています。
例題
Here's the translated content from the image and the Mermaid.js syntax to represent the diagrams:
### Translated Content for Notion
**Practice Problem**
In a certain programming language, an identifier starts with an English letter and is followed by any sequence of alphanumeric characters. When defined using BNF (Backus-Naur Form), which of the following can be included in "a"?
```bnf
To make a computer execute tasks, we write commands in programming languages (for more details, see p.348). As stated above, formal languages can be represented in this way. Let’s look at a simple example to see how formal languages are constructed. Suppose there is a rule that sentences are composed of the following structure: