Teoria da computação

1 Conceito 2 Linguagens Formais 2.1 Gramáticas 2.1.1 Alfabetos 2.1.2 Palavras ou cadeias 3 Referências

1.     Conceito

A Teoria da Computação é um ramo de estudo, tanto da computação teórica quanto da matemática, que lida com problemas que possam ser computados. Segundo Sipser (1997. p. 63) “Estudando esse assunto buscamos determinar o que se pode e o que não pode ser computado, quão rapidamente, com quanto de memória, e sobre que tipo de modelo computacional. O assunto tem conexões óbvias com a prática da engenharia, e, como em muitas ciências, ele também tem aspectos puramente filosóficos”.

Seu conceito teve início nos primeiros anos do século XX. Vale ressaltar o trabalho do matemático alemão David Hilbert, que, dentre os 23 problemas propostos por ele em 1900, o décimo buscava uma solução através de processos e um certo número finito de operações. Consensualmente no meio acadêmico, o que Hilbert buscava era uma solução através de um algoritmo.  

Mas foi em 1936 que, de modo independente, Alonzo Church e Alan Turing conseguiram, com um êxito inigualável até então, uma tese que estabelecesse a extensão e os limites da computação abstrata e definisse com mais clareza a definição de algoritmo. A tese de Church-Turing pode ser enunciada como:

 “Todo processo efetivo pode ser efetuado por uma máquina de Turing”.

Segundo Zimbarg (1987), essas máquinas materializam o arquétipo de um computador ideal. Consiste em uma fita infinitamente prolongável, dividida em espaços iguais, onde pode ser impressos ou apagados signos de um alfabeto finito. Com a máquina focalizando apenas um espaço por vez ela teria a autonomia de imprimir ou apagar, ir para à esquerda ou à direita do espaço enfocado e mudar instruções de seu funcionamento. Tudo isso sendo realizado através de um conjunto finito de instruções estabelecido anteriormente, trazendo à luz o conceito de programação, algoritmos, memória, e tantos outros conceitos que definem a teoria da Computação contemporânea.

2.     Linguagens Formais

Como vimos na seção anterior a Tese de Church-Turing estabeleceu os parâmetros e conceitos de termos utilizados hoje em teoria da Computação. Segundo a tese o algoritmo produz resultados somente em um número finito de passos, com um conjunto finitos de instruções simples e precisas, e com um número finito de símbolos. Para que isso se torne prático é essencial definir quais os símbolos serão utilizados no alfabeto, como os colocar à disposição, como será a interpretação do conjunto desses símbolos, entre outros aspectos. O estudo desse ramo da Teoria da Computação é definido como Teoria das Linguagens Formais e dos Autômatos. A Máquina de Turing é exemplo um autômato, sendo um interpretador de determinada linguagem e transformando-a em instrução.

Linguagens Formais são representadas de maneira finita e precisa. Seu sistema sempre é derivado de um modelo matemático. Esses modelos são necessários para que se classifique suas estruturas, características e relacionamentos entre si. Um modelo matemático conciso para a Teoria das Linguagens Formais deve fundamentar tanto aspectos teóricos: decidibilidade, complexidade computacional, computabilidades, como nas próprias aplicações (processamento de linguagens, reconhecimento de padrões, sistemas, etc). O conjunto de regras que vão produzir e especificar determinada linguagem dá-se o nome de Gramática.

2.1  Gramática

Como vimos acima, uma gramática define a representação de determinada linguagem. Em uma definição formal ela é formada de quatro elementos, a saber; G = (Vn, Vt, P, S).

Onde:

Vn – são as categorias sintáticas ou gramaticais;

 Vt – são as palavras utilizadas como símbolos da linguagem;

 P – são as regras sintáticas (ou gramaticais);

 S - é a categoria gramatical que sintetiza o que será produzido (gerado) pela gramática.

Formalizando a língua portuguesa teremos:

Vn = { <sentença> , <sujeito> , <predicado> , <substantivo> ,

<artigo> , <adjetivo> , <predicado> , <verbo> , <objeto> }

Vt = { joão, maria , cachorro, livro , pão, o , a , pequeno, bom , bela , morde , le , olha }

P = é o conjunto das regras gramaticais apresentado

S = <sentença>

Em 1956, o linguista estadunidense Noam Chomsky, em seu trabalho Syntatic Structures, classificou as gramáticas formais em 4 níveis, sendo os dois últimos (níveis 2 e 3) muito utilizados em linguagem de programação.

Os tipos de gramáticas seguindo a Hierarquia de Chomsky são:

Gramática Tipo 0: (ou gramática sem restrições, ou enumerável)

Gramática Tipo 1: (ou Gramática Sensível ao Contexto – G.S.C.)

Gramática Tipo 2: (ou Gramática Livre de Contexto – G.L.C.)

Gramática Tipo 3: (ou Gramática Regular – G.R.)

A Gramática do tipo 0 não há restrições. Geram linguagens infinitas que podem ser enumeradas.

2 Linguagens Formais 2.1 Gramáticas 2.1.1 Alfabetos 2.1.2 Palavras ou cadeias 3 Referências