Linguagem formal

Uma linguagem formal é um conjunto de palavras sobre um alfabeto, ou seja, dada uma linguagem $L$ sobre um alfabeto $\Sigma$, tem-se que $L\subseteq {\Sigma }^{\ast }$. Sendo assim, exemplos de linguagens formais sobre o alfabeto $\Sigma =\{a,b\}$ são: $\{\}$, $\{ϵ\}$, $\{a,b,aa,bb,aaa,bbb,...\}$ etc. O conjunto de todas as linguagens sobre um alfabeto $\Sigma$ é o conjunto das partições de $\Sigma$, ou seja: $2^{{\Sigma }^{\ast }}$.

Linguagens formais podem ser geradas a partir de gramáticas, que também definem sua classificação na Hierarquia de Chomsky.