# Introdução

Uma linguagem formal, ao contrário de uma linguagem natural, tem:
* Sintaxe bem definida: sempre se pode saber se uma sentença pertence à linguagem;
* Semântica precisa: não contém sentenças sem significado ou ambíguas.
As linguagens formais são úteis, não apenas na matemática, mas também nas áreas que utilizam a matemática como ferramenta, como as Engenharias, a Física, a Química e a Computação. No caso da Computação as linguagens formais são usadas diretamente pela maioria dos profissionais da área no dia a dia. Exemplos de linguagens formais são as linguagens Java, C, Pascal, HTML, etc. Desde o nível de instruções de máquina até os níveis altos da programação de um computador, as linguagens formais são uma presença constante.

# Conceitos Gerais

Um alfabeto (representado por $\Sigma$ (sigma) ou $\Gamma$ (gama)) é um conjunto finito não vazio de elementos que são referidos como símbolos. Uma palavra (também chamada cadeia - ou string, em inglês) sobre um alfabeto $\Sigma$ é uma sequência finita de símbolos de $\Sigma$. O tamanho de uma palavra $x$, $|x|$, é o número de símbolos que a compõe. A palavra vazia – constituída por zero símbolos – é designada por $\varepsilon$ (épsilon), logo $|\varepsilon |=0$.
   Exemplo 1: Dois exemplos de alfabetos são: $\Sigma =\{1\}$ e $\Gamma =\{0,1\}$. Exemplos de palavras sobre $\Sigma$ são $\varepsilon ,1,11,111$ etc. Já sobre $\Gamma$ podemos ter: $0,1,01,10,11,000$ etc.
Seja $a$ um símbolo. A notação $a^{n}$, onde $n\in \mathbb {N}$, é utilizada para designar uma palavra constituída de $n$ a’s em sequência. Assim, considerando o alfabeto $\Sigma$ do Exemplo 1, algumas de suas palavras podem ser assim escritas: $0^{3}=000$, $1^{2}=11$, $1^{0}=\varepsilon$, $1^{3}01^{2}=111011$ etc. Uma linguagem sobre um alfabeto $\Sigma$ é um conjunto de palavras sobre $\Sigma$. Se o conjunto de todas as palavras sobre $\Sigma$ é $\Sigma ^{*}$, então uma linguagem $L$ sobre $\Sigma$ é qualquer subconjunto de $\Sigma ^{*}$, i.e., $L\subset \Sigma ^{*}$.
   Exemplo 2: Seja o alfabeto $\Sigma =\{0,1\}$. O conjunto de todas as palavras sobre $\Sigma$ é $\Sigma ^{*}=\{\varepsilon ,0,1,00,01,10,11,000,...\}.$ São exemplos de linguagens sobre $\Sigma$:
   * $\emptyset$, linguagem que não contém nenhuma cadeia;
   * $\{\varepsilon \}$, linguagem que só contém a cadeia vazia;
   * $\{0\}$, contém somente uma única cadeia: 0;
   * $\{\varepsilon ,0\}$, contém duas cadeias: $\varepsilon {\text{ e }}0$;
   * $\{w\in \Sigma ^{*}|1\leq |w|\leq 5\}$, contém $\sum _{i=1}^{5}2^{i}$ cadeias;
   * $\{0^{n}|n{\text{ é par}}\}$, linguagem de tamanho infinito, já que existe uma infinidade de números pares;
   * $\{0^{n}1^{n}|n\in N\}$, linguagem constituída de toda palavra de tamanho par cuja primeira metade só contém 0s e a segunda metade só contém 1s.
   * $\{\Sigma ^{*}\}$, contém todas as palavras possíveis sobre o alfabeto $\Sigma$.
A maior parte das linguagens de interesse é infinita. E sua descrição envolve o uso de regras tais como as que foram apresentadas no Exemplo 2.

# Operações com linguagens

Sendo uma linguagem definida como um conjunto, é possível operar duas ou mais linguagens utilizando as mesmas operações definidas sobre conjuntos. Considere as linguagens L$_1$ e L$_2$ definidas sobre Σ$_1$ e Σ$_2$, respectivamente. Assim:
* L$_1$∪L$_2$={w | w∈L$_1$ ou w∈L$_2$ } é uma linguagem definida sobre Σ1∪Σ2;
* L$_1$∩L$_2$={w | w∈L$_1$ e w∈L$_2$ } é uma linguagem definida sobre Σ1∩Σ2;
* L$_1$-L$_2$={w | w∈L$_1$ e w∉L$_2$ } é uma linguagem definida sobre Σ1;
* O complemento de L$_1$ é L$_1$$^¯$={w | w∈Σ$^*$ e w∉L$_1$ }=Σ$^*$-L$_1$ e é uma linguagem definida sobre Σ$^*$.
Existem ainda outras operações tanto sobre palavras quanto sobre linguagens. A concatenação de duas palavras x=a$_1$a$_2$…a$_m$ e y=b$_1$b$_2$…b$_n$ é a palavra xy=a$_1$a$_2$…a$_m$b$_1$b$_2$…b$_n$. A operação de concatenação satisfaz as seguintes propriedades:
* Associatividade
* Elemento neutro à direta e à esquerda
Assim, sejam as palavras x,y,e z
   pela associatividade temos que x(yz)=(xy)z;
   pelo elemento neutro à direita e à esquerda temos que εw=wε=w para qualquer palavra w.
O reverso de uma palavra w=a$_1$a$_2$…a$_n$, w$^R$, é a sequência de símbolos na ordem inversa w$^R$=a$_n$a$_{n-1}$…a$_1$. Uma palavra tal que w=w$^R$ é um palíndromo. Seja uma palavra w=xyz, onde x, y e z podem ser ε ou não. A palavra z é uma subpalavra de w, x é um prefixo e y é um sufixo. Em particular, ε é prefixo, sufixo e subpalavra de qualquer palavra, e w é prefixo, sufixo e subpalavra de qualquer palavra w.
{Mostrar Exemplos}