Teoria da Computação

Teoria da Computação

Marino H. Catarino

Teoria da Computação

Copyright © 2023 by Marino H. Catarino

Todos os direitos reservados e protegidos pela Lei 9.610, de 19.2.1998.

É proibida a reprodução total ou parcial, por quaisquer meios, bem como a produção de apostilas, sem autorização prévia, por escrito, da Editora.

Direitos exclusivos da edição e distribuição em língua portuguesa:

Maria Augusta Delgado Livraria, Distribuidora e Editora

Direção Editorial: Isaac D. Abulafia

Gerência Editorial: Marisol Soto

Diagramação e Capa: Madalena Araújo

Dados Internacionais de Catalogação na Publicação (CIP)

de acordo com ISBD

Elaborado por Odilio Hilario Moreira Junior - CRB-8/9949

Índice para catálogo sistemático:

1. Ciência da Computação 004

2. Ciência da Computação 004

atendimento@freitasbastos.com

www.freitasbastos.com

Sumário

1. Introdução

1.1. Fundamentos dos Conjuntos

1.2. Conclusões

2. Gramática

2.1. Alfabeto

2.2. Cadeia

2.3. Linguagem

2.4. Gramática

2.5. Definição da Gramática

2.6. Classes gramaticais

2.7. Conclusões

3. Linguagem

3.1. Definindo a linguagem

3.2. Linguagem regular

3.3. Autômato finito

3.4. Conclusões

4. Expressões e Gramáticas Regulares

4.1. Definição de Expressões regulares

4.2. Gramática regular

4.3. Lema do Bombeamento

4.4. Conclusões

5. Linguagem Livre de Contexto

5.1. Gramática Livre de Contexto

5.2. Árvore de derivação

5.3. Representação Backus-Nahur Form (BNF)

5.4. Forma normal de Chomsky

5.5. Autômato de Pilha

5.6. Conclusões

6. Linguagem Sensível ao Contexto

6.1. Gramática Sensível ao Contexto

6.2. Máquina de Turing

6.3. Autômato Linearmente Limitado

6.4. Conclusões

7. Computabilidade

7.1. Definindo a Computabilidade

7.2. História da Computação

7.3. Tese de Church-Turing

7.5. Problemas computáveis e não computáveis

8. Decidibilidade

8.2. Linguagens Recursivas

8.3. Linguagens Recursivamente Enumeráveis

8.4. Problemas indecidíveis

8.5. Redutibilidade

8.6. Teorema de Rice

8.7. Conclusões

9. Complexidade Computacional

9.1. Definindo a complexidade

1. Introdução

A área da computação obteve uma visibilidade muito grande no começo do século 21, novos termos, conceitos e funcionalidades possibilitaram popularizar termos antes desconhecidos. Expressões como Inteligência Artificial, Big Data, Internet das Coisas ou Computação em Nuvem se expandiram para diversos setores de atuação.

A aceitação e disseminação de dispositivos móveis permitiu que novas áreas de negócio fossem impactadas com aplicativos digitais, tais como serviços de entrega de comidas ou produtos e de realizar exames laboratoriais sem precisar sair de casa.

Os sistemas bancários e financeiros evoluíram muito graças às tecnologias. O que antes era necessário ir presencialmente aos bancos agora é possível acessar um aplicativo em qualquer local e realizar as transações bancárias com as devidas seguranças, garantindo assim a melhoria e conforto do serviço ofertado.

Com a evolução tecnológica e a inserção de novos segmentos, a necessidade dos programas de computadores aumentou muito. Para implementar estas soluções foram desenvolvidas as linguagens de programação, as quais permitem criar programas para executar tarefas computacionais.

A primeira linguagem de programação imperativa e seu primeiro compilador foi o FORTRAN, desenvolvido para o IBM e apresentado na década de 50 do século passado. Nos anos seguintes outras linguagens de programação como ALGOL, COBOL, C foram sendo divulgadas. Com o passar dos anos surgiram muitas outras linguagens de programação. Podemos mencionar JavaScript, Python, Java, PHP, CSS, C#, C++ e C entre muitas outras.

Cada uma destas linguagens de programação possui sua sintaxe e comandos próprios, com isto requisitando um aprendizado específico que possibilite utilizá-las no desenvolvimento de programas de computador. Ou seja, não basta aprender a programar em uma determinada linguagem para saber programar em outra, é preciso estudar cada uma delas individualmente.

Podemos fazer um comparativo entre a linguagem de programação e a linguagem utilizada para comunicação. Precisamos aprender francês para conseguir escrever em francês e da mesma forma é preciso aprender alemão para escrever em alemão. Não basta saber as regras gramaticais e o vocabulário em francês que se aprende e escreve em alemão.

Apesar de o francês e do alemão serem bem diferentes, ambos utilizam o mesmo alfabeto e possuem similaridade quanto as suas classes gramaticais, por exemplo, ambas as línguas possuem verbos, substantivos, artigos e pronomes. É possível aprender os principais verbos em cada língua e as principais frases e conseguir se comunicar com eles. Por exemplo, os verbos para comprar, dormir, vender e valor.

O mesmo ocorre com as linguagens de programação. Apesar de os princípios serem os mesmos, é preciso aprender cada linguagem de programação individualmente para poder utilizá-la.

Esta é uma das importâncias de teoria da computação, apresentar os principais conceitos relacionados com a criação de linguagens de programação e na concepção de seu uso para elaborar determinadas tarefas, visando solucionar problemas.

Através da compreensão do que é a gramática e das regras que definem uma linguagem é possível elaborar programas mais complexos de computação para a execução de tarefas mais complicados.

Ao longo deste e dos próximos capítulos iremos explorar os principais conceitos e fundamentos referentes à teoria da computação, apresentando o conteúdo de uma forma simples para que seja possível assimilar o conhecimento e empregá-lo independente da linguagem ou área de atuação escolhida.

1.1. Fundamentos dos Conjuntos

Para ser possível uma boa compreensão de alguns assuntos é preciso conhecer os fundamentos que nos possibilite ter uma compreensão melhor do assunto. Um conceito muito importante da matemática e que vamos utilizar amplamente em teoria da computação é o de conjuntos.

Podemos definir conjunto como um grupo de objetos sem repetição ou uma ordenação específica que podem ser representados como uma unidade. Estes objetos são denominados de elementos de um conjunto, por exemplo, o conjunto das vogais possui como elementos: a, e i, o u.

O conjunto de todos os elementos que podem ser considerados em um estudo é chamado de Conjunto Universo. Como exemplos de Conjunto Universo podemos ter um universo composto de todas as letras do alfabeto, onde o conjunto das vogais contém apenas as vogais.

Outro exemplo de Conjunto Universo são os números inteiros, onde podemos ter um conjunto dos números pares pertencente a este universo.

1.1.1. Representação dos conjuntos

Uma convenção quanto ao conceito dos conjuntos é que estes sejam representados usando letras maiúsculas e os elementos por letras minúsculas. Nesta notação o Conjunto Universo é representado pela letra U.

Utilizando esta convenção o conjunto das vogais pode ser representado pelo conjunto A que contém os elementos a, e, i, o e u. Uma representação de conjunto (notação) é:

Como um conjunto de números finitos não tem ordenação, a ordem de apresentação dos elementos não tem importância. Por exemplo, o conjunto A pode ser representado da seguinte forma:

Os conjuntos A e B representam o mesmo conjunto, temos uma relação de igualdade entre eles. Esta relação ocorre quando dois conjuntos possuem exatamente os mesmos elementos. Podemos representar dois conjuntos iguais da seguinte forma:

Quanto à quantidade de elementos que podem estar contidos em um conjunto, existe um tipo específico que é o conjunto unitário, este conjunto é composto por um único elemento. Por exemplo, o conjunto:

Onde B é o conjunto unitário determinado pelo elemento x.

Também podemos ter conjuntos que não possuem nenhum elemento e são denominados conjuntos vazios, sendo representados pelo símbolo Ø.

A representação matemática dos elementos e dos conjuntos pode ser melhor compreendida utilizando o diagrama de Venn, que é uma representação gráfica proposta pelo matemático e filósofo britânico John Venn (1834-1923). O diagrama de Venn utiliza formas geométricas para representar os elementos de um conjunto.

As principais representações são:

Conjunto universo: representado por umretângulo.

Conjunto: a representação de um subconjunto de um conjunto universo é feita utilizando umcírculo.

Elementos: os elementos de um conjunto são representados inseridos dentro doscírculos.

Na figura 1 vemos as representações do conjunto universo (a) e de um conjunto A inserido no conjunto universo (b):

Figura 1: Diagrama de Venn para representar os conjuntos

Fonte: Autoria própria.

A representação do conjunto das vogais A pode ser visto na figura 2:

Figura 2: Representação do Conjunto A

Fonte: Autoria própria.

1.1.2. Relação de Pertinência

A relação de pertinência se refere a indicar se um elemento pertence ou não a um determinado conjunto. Para isto utilizamos dois símbolos, são eles: ∈ (pertence) e ∉ (não pertence).

Por exemplo, considerando o conjunto A das vogais: podemos representar que o elemento u pertence a este conjunto da seguinte forma:

Quanto à representação de que um elemento x não pertence ao conjunto das vogais A temos:

Quando temos que mais de um elemento pertencem a um mesmo conjunto, podemos representar utilizando uma única ocorrência do símbolo de pertinência. Por exemplo, os elementos a, e u pertencem ao conjunto A, então podemos escrever:

a, u ∈ A, ou seja, a ∈ A e u ∈ A.

1.1.3. Família de Conjuntos

Uma família de conjuntos se refere a quando os elementos que fazem parte de um conjunto são também outros conjuntos. Para exemplificar vamos considerar os seguintes elementos:

Estes elementos fazem parte do conjunto T:

Com relação ao pertencimento, temos:

{a, b, c} ∈ T e {z, w} ∈ T

Em uma família de conjuntos T os elementos que compõe os conjuntos não pertencem ao