Teoria da Computação/Linguagens

Fonte: Wikiversidade
Saltar para a navegação Saltar para a pesquisa

Introdução[editar | editar código-fonte]

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 a 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[editar | editar código-fonte]

Um alfabeto (representado por (sigma) ou (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 é uma sequência finita de símbolos de . O tamanho de uma palavra , , é o número de símbolos que a compõe. A palavra vazia – constituída por zero símbolos – é designada por (épsilon), logo .

Exemplo 1: Dois exemplos de alfabetos são: e . Exemplos de palavras sobre são etc. Já sobre podemos ter: etc.

Seja um símbolo. A notação , onde , é utilizada para designar uma palavra constituída de a’s em sequência. Assim, considerando o alfabeto do Exemplo 1, algumas de suas palavras podem ser assim escritas: , , , etc. Uma linguagem sobre um alfabeto é um conjunto de palavras sobre . Se o conjunto de todas as palavras sobre é , então uma linguagem sobre é qualquer subconjunto de , i.e., .

Exemplo 2: Seja o alfabeto . O conjunto de todas as palavras sobre é São exemplos de linguagens sobre :

  • , linguagem que não contém nenhuma cadeia;
  • , linguagem que só contém a cadeia vazia;
  • , contém somente uma única cadeia: 0;
  • , contém duas cadeias: ;
  • , contém cadeias;
  • , linguagem de tamanho infinito, já que existe uma infinidade de números pares;
  • , linguagem constituída de toda palavra de tamanho par cuja primeira metade só contém 0s e a segunda metade só contém 1s.
  • , contém todas as palavras possíveis sobre o alfabeto .

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[editar | editar código-fonte]

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 L1 e L2 definidas sobre Σ1 e Σ2, respectivamente. Assim:

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

Existem ainda outras operações tanto sobre palavras quanto sobre linguagens. A concatenação de duas palavras x=a1a2…am e y=b1b2…bn é a palavra xy=a1a2…amb1b2…bn. 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=a1a2…an, wR, é a sequência de símbolos na ordem inversa wR=anan-1…a1. Uma palavra tal que w=wR é 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}

Tipos de Linguagens[editar | editar código-fonte]