Exibir código-fonte para Teoria da computação

== 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: <nowiki>http://rmu.sbm.org.br/Conteudo/n06/n06_Artigo01.pdf</nowiki>

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: <nowiki>https://www.ime.usp.br/~jef/tc_gramaticas.pdf</nowiki> 

<nowiki>https://pt.wikipedia.org/wiki/Linguagem_formal</nowiki>

<nowiki>https://pt.wikipedia.org/wiki/Gram%C3%A1tica_formal</nowiki>

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