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.
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.
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 Tipo 0 não há restrições. Geram linguagens infinitas que podem ser enumeradas. Sendo infinita, é uma linguagem formal utilizada pela máquina de Turing. O décimo problema de Hilbert também abrange essa classe de linguagem. Também chamada de Turing-reconhecível.
Já nas Gramáticas Tipo 1 tanto o lado esquerdo ou direito podem ser cercados por um contexto de símbolo terminal e de símbolo não terminal. Também chamada de Gramática Sensível ao Contexto.
As Gramáticas de Tipo 2, diferente das do Tipo 1, definem que o símbolo não terminal do lado esquerdo pode ser sempre substituído pelo o símbolo do lado direito (A à a). Também chamada de Gramática Livre de Contexto.
Finalizando, as Gramáticas de Tipo 3, são também chamadas de Gramáticas Regulares. Pode-se criar linguagens bem definidas para compiladores, principalmente por obterem reconhecedores simples.
Alfabetos
Para cada tipo de gramática citado existem inúmeros tipo de linguagens formadas por alfabetos específicos podendo ter alfabetos infinitos ou não. Resumindo, conjuntos e subconjuntos reunidos de alfabetos formam uma linguagem. Vejamos alguns exemplos:
A linguagem recursivamente enumerável é uma linguagem de gramática tipo 0 para qual existe uma máquina de Turing que enumera todas as cadeias válidas da linguagem podendo ser infinita. Diferente da linguagem recursiva, a linguagem sensível ao contexto, linguagem de gramática tipo 1, teria uma também uma máquina de Turing transcrevendo algoritmos mas com a diferença que esse autômato seria limitado linearmente (tendo memória finita), com seu alfabeto limitado também.
As linguagens de livre contexto (gramática tipo 2) são aceitas por um autômato de pilhas. Já as linguagens regulares (de gramática tipo 3) são as mais complexas sendo aceitas por vários tipos de autômatos, inclusive máquinas de Tuning, e por monoides (estruturas algébricas que podem ser usadas em ciência da computação).
Palavras ou cadeias
Palavras ou cadeias são uma sequência de comprimento no alfabeto. A principal operação feita com essas sequências é a concatenação. Um exemplo de concatenação seria: x + y = xy. São utilizadas para dar sentido as linguagens e são regradas pelo domínio da gramática a qual pertence.
Referências:
ZIMBARG, Jacob. Aspectos da Tese Church-Turing. Instituto de Matemática, USP, 1987. Disponível no link: http://rmu.sbm.org.br/Conteudo/n06/n06_Artigo01.pdf
SIPSER, Michael. Uma Introdução à Teoria da Computação. Traduzido do original por Ruy J. Guerra B. de Queiroz, 1987
FURTADO, Olinto José Varela. Linguagens Formais e Compiladores. Disponível no link: https://www.ime.usp.br/~jef/tc_gramaticas.pdf
https://pt.wikipedia.org/wiki/Linguagem_formal
https://pt.wikipedia.org/wiki/Gram%C3%A1tica_formal
https://pt.wikipedia.org/wiki/Teoria_dos_aut%C3%B4matos
https://pt.wikipedia.org/wiki/Gram%C3%A1tica_livre_de_contexto
https://pt.wikipedia.org/wiki/Gram%C3%A1tica_sens%C3%ADvel_ao_contexto