Teoria da computação: mudanças entre as edições

Edição atual tal como às 12h17min de 7 de junho de 2017

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

@@ Linha 1: / Linha 1: @@
 == Conceito ==
-Teoria da computação é um ramo responsável em lidar com a eficiência que problemas podem ser resolvidos em um modelo computacional, usando algoritmos.
+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”.
-Cientistas da computação trabalharam com uma abstração matemática de computadores chamado modelo de computação. Diferentes modelos foram propostos, mas utilizado é a Máquina de Turing.
+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.
-A teoria da computação é o ramo que estuda os modelos genéricos de computação, assim como os limites da computação.
+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:
-O modelo computacional atual é incapaz de reconhecer a linguagem humana direta, pois é uma linguagem ambígua, ou seja, uma mesma palavra pode representar diferentes significados de acordo com o contexto.
+ ''“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 ==
-Com objetivo de aproximar a linguagem humana das linguagens compreensíveis pelos computadores, foram criadas as linguagens de programação. Estas são linguagens formais, que visam remover todo tipo de ambiguidade, garantindo que cada palavra reservada tenha uma unica função independente de onde seja usada. Assim como a linguagem humana, as linguagens formais também possuem sua própria gramática.
+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áticas ==
+'''''Gramática Tipo 0: (ou gramática sem restrições, ou enumerável)'''''
-Assim como a linguagem humana, as linguagens formais também possuem sua própria gramática, que ditam o que é valido ou não no contexto das linguagens formais, ou seja, um conjunto de regras formadas a partir do alfabeto da linguagem que validam a sintaxe de determinada linguagem.
+'''''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 ===
-O alfabeto pode ser compreendido em um conjunto finito de símbolos válidos no contexto da linguagem.
+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:
-Nas linguagens formais o alfabeto pode ser representado pela letra grega maiúscula sigma (Σ).
+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.
-Exemplo: Σ = {0,1} representa o alfabeto composto pelos símbolos 0 e 1
+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 ===
-As palavras ou cadeias podem ser compreendidas como um conjunto de símbolos do alfabeto, concatenados.
-O comprimento de uma cadeia ou palavra pode ser representado como |w|.
-Uma palavra ou cadeia com comprimento 0 (vazia) pode ser representada pela letra grega minúscula epsilon (ε).
+'''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>
-O símbolo Σ* representa todas as cadeias ou palavras possíveis de serem representadas pelo alfabeto Σ inclusive a palavra vazia ε.
+<nowiki>https://pt.wikipedia.org/wiki/Linguagem_formal</nowiki>
-Exemplo: w = 10101 é uma palavra, e |w| = 5.
+<nowiki>https://pt.wikipedia.org/wiki/Gram%C3%A1tica_formal</nowiki>
-== Referências ==
+https://pt.wikipedia.org/wiki/Teoria_dos_aut%C3%B4matos
-LEWIS, Harry R. & PAPADIMITRION, Christos H. Elementos de Teoria da Computação. 2.ed. Porto Alegre, Bookman, 2000.
-MENEZES, Paulo Blauth. Linguagens formais e autômatos. 2.ed. Porto Alegre, Sagra Luzzatto, 1998. 165p
-HOPCROFT, John E.; ULLMAN, Jeffrey D.; MOTWANI, Rajeev. Introdução à Teoria de Autômatos, Linguagens e Computação; Rio de Janeiro; Ed. Campus, 2002.
+https://pt.wikipedia.org/wiki/Gram%C3%A1tica_livre_de_contexto
-DIVERIO, T. A.; MENEZES, P. B. Teoria da Computação: Máquinas Universais e Computabilidade, Série Livros Didáticos Número 5, Instituto de Informática, da UFRGS, Editora Sagra Luzzatto, 1a edição, 1999.
+https://pt.wikipedia.org/wiki/Gram%C3%A1tica_sens%C3%ADvel_ao_contexto