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