形式言語
自然言語を比較的単純な形式言語のモデルにあてはめて分析する言語学は、チョムスキーによって提唱された。音素や語幹などを素記号として考える。 実際の自然言語の構文規則(あるいは文法)は、文字通り自然発生的のものであり、形式言語における構文規則のように明確に規定するのは難しい。
ただ、素朴な文法論の主張は、形式言語の理論とみなすことができる。 素朴な文法論は、例えば次のようなものである。
品詞にはこのようなのものがある。
この語はあの品詞に属す。
この品詞に属す語をこの活用と組み合わせと順序とで並べると文(や句や節)になる。
こういう文法論はすなわち、素記号とは何かを定め、それらから文を作る構文規則を定めるのだから、まさに形式言語の理論である。
こういう形式言語論的な文法論は、実際の言語と比較することで自然言語の特徴を浮き彫りにし、自然言語のより深い理解へと導くことを可能とすることもなくはない。言語そのものではなく、言語行動の深層をなす人間精神を探るためには、むしろこういう文法論を数学化し、更に意味論・文法論を伴った論理学にまで推し進めることが有意義ともいえよう。
形式言語の理論、特にオートマトン理論と関連したそれにおいては、言語はアルファベットの列(語 word) の集合である。
L ⊂ Σ ∗ = { ⟨ σ 1 , σ 2 , . . . ⟩ | σ i ∈ Σ } {\displaystyle L\subset \Sigma ^{*}=\{\langle \sigma _{1},\sigma _{2},...\rangle |\sigma _{i}\in \Sigma \}}
ただし、長さゼロの空単語(Empty Word, 記号 e {\displaystyle e} 、 ε {\displaystyle \epsilon } 、 Λ {\displaystyle \Lambda } )も含む。 チューリングマシンの言語は単なる文字列なので、数学的構造(他のチューリングマシンを含む)を扱うには符号化(エンコード)し、その数値を解釈するプログラムを埋め込む必要がある。 チューリング完全機械は十分強力なので、この手法であらゆる列挙可能な構造を扱うことができる。チューリングマシンの数値表現については(チューリングマシンの)表記(description)という。
あるチューリングマシンが存在して、言語に属するすべての語 w に対して動作させると受理状態で停止し、属さない語には受理しないようなとき、その言語はチューリング認識可能という。 また、言語に属さないときは必ず拒否状態で停止する場合、その言語はチューリング判別可能であるという。