linguagens formais → maneira de descrever regras gramaticais de uma linguagem.
grafos → diferente das árvores, os grafos representam regras para algo.
linguagem → qualquer meio sistemático capaz de comunicar qualquer coisa a partir de qualquer meio.
formal → meio definido por regras.
autômato →maquina que funciona de forma automática. Nesse contexto, os grafos são autômatos, uma vez que, não importa se alguém sabe ou não as regras de uma linguagem, apenas seguindo o grafo é capaz de dizer seu uma palavra é válida ou não de forma automática. Em um contexto mais geral, um robô pode ser considerado um autômato, uma vez que ele seguirá apenas o que foi anteriormente programado, também de forma automática.
alfabeto → conjunto de símbolos que pertencem à uma linguagem. Exemplo:{0,1}.
cadeia → sequência de símbolos. Exemplo: 0101010000101010.
autômatos finitos
- modelo computacional com quantidade limitada de estados;
- pode ser representado por tabelas também;
- pode ser implementado com poucos recursos;
- caso o último símbolo seja um estado final a palavra é válida;
- reconhece uma linguagem;
autômatos finitos determinísticos → autômato finito que há apenas um caminho entre 2 estados para cada símbolo possível.
Partes de um autômato finito
- M = (Q, ∑, δ, q0, F)
- Q → Conjunto de estados
- ∑ → alfabeto
- δ → função de transição
- q0 → estado inicial (não pode haver mais de um)
- F → conjunto de estados finais
Símbolos
transições
observe que, os valores ficam nas transições, não nos estados.