DC-UFRPE/Bacharelado em Ciência da Computação/Teoria da Computação/Linguagens e Cadeias

Introdução

Uma linguagem formal, ao contrário de uma linguagem natural, tem:

1. Sintaxe bem definida: sempre se pode saber se uma sentença pertence à linguagem;
2. 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₁ e L₂ definidas sobre Σ₁ e Σ₂, respectivamente. Assim:

• L₁∪L₂={w | w∈L₁ ou w∈L₂ } é uma linguagem definida sobre Σ1∪Σ2;
• L₁∩L₂={w | w∈L₁ e w∈L₂ } é uma linguagem definida sobre Σ1∩Σ2;
• L₁-L₂={w | w∈L₁ e w∉L₂ } é uma linguagem definida sobre Σ1;
• O complemento de L₁ é L₁^¯={w | w∈Σ^* e w∉L₁ }=Σ^*-L₁ e é uma linguagem definida sobre Σ^*.

Existem ainda outras operações tanto sobre palavras quanto sobre linguagens. A concatenação de duas palavras x=a₁a₂…a_m e y=b₁b₂…b_n é a palavra xy=a₁a₂…a_mb₁b₂…b_n. A operação de concatenação satisfaz as seguintes propriedades:

1. Associatividade
2. 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₁a₂…a_n, w^R, é a sequência de símbolos na ordem inversa w^R=a_na_n-1…a₁. 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.