形式言語
形式言語は、形式文法と密接な関係がある。例として、次のような文脈自由文法の構文規則があるとき、
名詞句 ::= 名詞 | 形容詞 名詞 | 名詞句 "を" 動詞 "ている" 名詞句
動詞 ::= "見"
名詞 ::= "猿" | "飼育員"
形容詞 ::= "小さい"
以下のように規則を再帰的に適用して、その言語の要素(名詞句)を列挙することができる。
(猿 飼育員 小さい猿 小さい飼育員)
(猿 飼育員 小さい猿 小さい飼育員 猿を見ている猿 猿を見ている飼育員 猿を見ている小さい猿 ... 小さい猿を見ている猿 ...)
(猿 飼育員 小さい猿 小さい飼育員 猿を見ている猿 ... 猿をみている猿を見ている猿 ... 小さい猿を見ている猿を見ている小さい飼育員を見ている猿 ...)
...
すなわち、このような操作の任意回の繰り返しによって、その言語(文の集合)が得られる。
また、形式文法が階層をなすというチョムスキー階層は、生成する言語では言語の認識に必要な最小のオートマトンが階層をなすという形で現れる。
L 1 {\displaystyle L_{1}} と L 2 {\displaystyle L_{2}} の「シャッフル」とは、 v 1 w 1 v 2 w 2 . . . v n w n {\displaystyle v_{1}w_{1}v_{2}w_{2}...v_{n}w_{n}} で表される全文字列から構成される。ここで、 n ≥ 1 {\displaystyle n\geq 1} で、 v 1 , . . . , v n {\displaystyle v_{1},...,v_{n}} を連結した v 1 . . . v n {\displaystyle v_{1}...v_{n}} は L 1 {\displaystyle L_{1}} に含まれる文字列であり、 w 1 , . . . , w n {\displaystyle w_{1},...,w_{n}} を連結した w 1 . . . w n {\displaystyle w_{1}...w_{n}} は L 2 {\displaystyle L_{2}} に含まれる文字列である。
モデル理論においては、言語は定数記号、関数記号、述語記号の集合である。
L = { c 0 , c 1 , . . . } ∪ { f 0 , f 1 , . . . } ∪ { p 0 , p 1 , . . . } {\displaystyle L=\{c_{0},c_{1},...\}\cup \{f_{0},f_{1},...\}\cup \{p_{0},p_{1},...\}}