As Linguagens Formais e Autômatos

Universidade do Estado do Mato Grosso – UNEMAT

Núcleo Pedagógico de Rondonópolis

Ciência da Computação – 2º semestre

Discente: Lucas Angelo Mattesco

Docente: Prof. Me. Dárley Domingos de Almeida

Disciplina: Linguagens Formais e Autômatos

Aula 1

Introdução – A priemira aula abordou diferentes assuntos, desde técnicas de estudo, conforme os ensinamentos do professor Pierluigi Piazzi, até informações sobre a disciplina e o curso de Ciência da Computação

“Programar, em Ciência da Computação, é o processo de escrita, teste e manutenção de um programa de computador.”

Linguagens de programação: método padronizado para comunicar instruções a um computador, a partir de um conjunto específico de regras de sintaxe (estrutura) e semântica (significado).

Taxonomia das Linguagens de Programação:

• Abstração (entendimento do programador)

• Alto nível (ex. C++) – linguagem humana
• Baixo nível (ex. Assembly) – linguagem de máquina

[pic 1]

• Paradigma (modo pelo qual o programador irá guiar-se quando for construir um programa de computador)

• Estruturado/imperativo
• Orientado a objetos

• Ambiente

• Desktop
• Web

[pic 2]

[pic 3]

[pic 4]

As linguagens são uma forma de comunicação constituídas por um conjunto de elementos (alfabeto) e métodos (regras), que são usados e entendidos por uma comunidade, porém passíveis de ambiguidade (mais de um entendimento dependendo do contexto).

[pic 5]

Já as linguagens formais são linguagens artificiais com regras específicas e formais que garantem a não ambiguidade (ambiguidade = múltiplos sentidos para uma mesma frase), usando expressões regulares)

        Autômato: representação gráfica de expressões regulares.

Interpretador: traduz o código em tempo real, linha a linha, na medida em que o programa é utilizado, ou seja, os erros só são detectados quando a linha de código defeituosa é executada. Usa menos memória, tem um pré-processamento mais rápido mas um processamento mais lento.

        Compilador: traduz todo o código de uma só vez, gerando um arquivo executável (Windows). Só pode ser executado/compilado caso não haja nenhum erro.

---

Aula 2

Conjunto: “coleção ou agrupamento bem definido de objetos/elementos de qualquer classe.”

Notação: A = {1; 2; 3; 4; ...}

• Os elementos são agrupados com ponto e vírgula (;)
• O conjunto é denominado por uma letra maiúscula.

Cardinal do conjunto: número de elementos distintos do conjunto.

• Q = {0; 0; 1; 1} = {0; 1}
• n(Q) = 2

Determinação de conjuntos:

• Por extensão: indicar todos os elementos.

• Ex.: A = {0; 1; 2; 3; 4; 5; 6; 7; 8; 9}

• Por entendimento: mediante uma propriedade.

• Ex.: A = {x | x = algarismo}

Diagrama de Venn: representar conjuntos de maneira gráfica.

Conjuntos especiais

• Conjunto vazio: não tem elementos ([pic 6] ou { })
• Conjunto unitário: tem um só elemento.
• Conjunto finito: número limitado de elementos.
• Conjunto infinito: infinitos elementos.
• Conjunto universal (U): todos os elementos de uma situação particular

Relação de pertinência (entre elemento e conjunto):

• [pic 7]   pertence
• [pic 8]   não pertence

Relação de inclusão (entre conjuntos)

• [pic 9] / [pic 10] está contido / não está contido
• [pic 11] /  ⊅   contém / não contem
• Propriedades:

• 1) Todo conjunto está incluído em si mesmo.
• 2) O conjunto vazio está incluído em todos os conjuntos.
• 3) A está contido em B = B contém A
• 4) A está contido em B se e somente se para todo elemento que pertence a A, tal elemento pertence a B

Relacão complementar (entre conjuntos)

• Complementar de A em relação a B: conjunto formado pelos elementos que pertencem a A e não pertencem a B.

Igualdade (entre conjuntos)

• Dois conjuntos são iguais se têm exatamente os mesmos elementos.

Conjuntos disjuntos (entre conjuntos)

• Dois conjuntos são disjuntos quando não têm elementos em comum.

Conjunto potência (P(A))

• Conjunto formado por todos os subconjuntos de um conjunto.
• n(P(A)) = 2^n

União de conjuntos (∪)

• Conjunto formado por todos os elementos dos conjuntos especificados.

Conjuntos comparáveis

• Dois conjuntos são comparáveis se entre eles existe uma relação de inclusão

Intersecção de conjuntos (∩)

• Todos os elementos que pertencem simultaneamente a dois conjuntos.

Diferença de conjuntos (A – B)

• Sendo a operação A – B, a diferença é composta por todos os elementos que pertencem a A e não pertencem a B.

Diferença simétrica (A Δ B)

• Todos os elementos que pertencem a (A – B) ou (B – A).

Complemento de um conjunto (A’)

• Conjunto formado pelos elementos do conjunto universo (U) que não pertencem ao conjunto A.
• U – A

Conjunto de conjuntos

• Conjunto cujos elementos são conjuntos.
• Ex.: A = { {a}; {b}; {a; b}}

Conjuntos numéricos

[pic 12]

Aula 3

História

• Alan Turing (1930’s)

• Estudou os limites de uma máquina abstrata equivalente aos computadores atuais.

• 1940-1950’s

• Estudos em autômatos finitos para modelar o cérebro.

• Noam Chomsky (1950’s)

• Gramáticas formais.

• S. Cook (1969)

• Teoria da Complexidade – o que é possível ou não computar.

Alfabeto: conjunto de símbolos (elementos) (geralmente Σ – sigma)

• não-vazio
• finito

Cadeia/palavra: sequência finita construída com símbolos de um alfabeto.

• s:[n] -> Σ
• s – sequência de símbolos
• [n] – comprimento – pode ser representado como |s|
• Σ – alfabeto
• ex.: Σ = {a; b} -> cadeias: (a), (aa), (b), (ab)...
• Σ = {a, b, c} e s = cbba

• s:[4] -> Σ
• s(1) = c
• s(2) = b
• s(3) = b
• s(4) = a

Cadeia vazia: nenhum símbolo (λ ou ε).

...