問題
CFG（文脈自由文法）に関する記述として適切なものはどれか。
選択肢
- 1正規表現で表せる言語の集合と完全に一致する
- 2プログラミング言語の構文記述に広く用いられる
- 3チューリングマシンと等価な計算能力を持つ
- 4左再帰を含むことができない
正解
2. プログラミング言語の構文記述に広く用いられる
詳しい解説を見る解説を閉じる
解説
文脈自由文法（CFG: Context-Free Grammar）は、BNF記法等でプログラミング言語の構文定義に用いられる。チョムスキー階層のType2に位置し、正規言語（Type3）より表現力が高いが、文脈依存言語（Type1）より弱い。プッシュダウンオートマトンと等価。LR構文解析器等で実装される。
一問一答
全400問を繰り返し学習