ftc apostila

Alfabeto - ∑

Conjunto de símbolos
Sequência finita de símbolos de um alfabeto ∑
Concatenação de strings

Subconjunto de todas as strings que podem ser formadas sobre um alfabeto ∑

String

Operações

Concatenação

Reverso

Podem ser processados por máquinas abstratas chamadas de máquinas de estado finito.
Definições

Q é o conjunto finito de estados

Especificação de Linguagens
Linguagens

Pode ser especificada utilizando da construção de conjuntos.

Fundamentos
Teóricos
da
Computação

∑ é o conjunto finito dos símbolos, chamado alfabeto. q0 ∈ Q é o estado inicial
M = (Q, ∑, g, q0, F), onde:
Autômatos Finitos

Uma lingua gem é regular se ela é definida por um conjunto regular!

Compreendem uma família de linguagens que tem um papel importante em linguagens formais, reconhecimento de padrões e na teoria de máquinas de estado finito.

Possuem uma propriedade necessária a computação mecânica, o determinismo!

Imaginando de forma mecânica consiste de: um único registrador interno, um conjunto de valores para o registrador, uma fita, uma leitora de fita e um conjunto de instruções.

A especificação de uma linguagem deve ser uma descrição sem ambiguidade das strings que a compõem.

Conjunto regular sobre um alfabeto ∑, é aquele que pode ser obtido pelos elementos base: ∅, {∊}, e { a | para todo a ∈ ∑ }; e pela aplicação finita das operações de união, concatenação e fecho de Kleene nos elementos base.

Máquinas abstratas são os fundamentos do projeto, e que não incluem os detalhes de implementação. O objetivo da computação de um autômato é determinar a aceitabilidade da string de entrada.

As linguagens interessantes são aquelas que satisfazem alguma sintaxe pré-requerida

Pode ser especificada por uma definição recursiva, contudo, esta ferramenta não é adequada para garantir as complexidades sintáticas das linguagens naturais e computacionais. (uv)w = u(vw)

R
R
(uv) = v uR

Operações

X* = {