|
|
| Linha 1: |
Linha 1: |
| 1 Conceito | | 1 |
| 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 Linguagens Formais 2.1 Gramáticas |
| 2.1.1 Alfabetos 2.1.2 Palavras ou cadeias 3 Referências | | 2.1.1 Alfabetos 2.1.2 Palavras ou cadeias 3 Referências |
1
2 Linguagens Formais 2.1 Gramáticas
2.1.1 Alfabetos 2.1.2 Palavras ou cadeias 3 Referências