EDIT 1: Não consegui deixar as imagens disponíveis no post por muito tempo, então, para que vocês não fiquem sem referências, deixei o link contendo as imagens.

Introdução

Todos nós sabemos que a área de TI é muito ampla e variada, quando se trata de programação muito se fala de qual a melhor stack, qual melhor curso, estrutura de dados, como criar apps revolucionários se vale a pena ou não fazer faculdade pra ser programador e etc...

Mas poucos falam de tópicos que são fundamentais, que um dia mudaram o mundo e ainda estão mudando, um deles é Linguagens Formais e Autômatos, que irei tentar abordar aqui hoje.

Por que estudar autômatos e para que serve?

Há várias razões pelas quais o estudo de autômatos e complexidade é uma parte importante do núcleo de Ciência da Computação, Autômatos finitos constituem um modelo útil para muitos elementos importantes de hardware e software, vou listar a baixo alguns dos elementos mais importantes:

1. Software para projetar e verificar comportamento de circuitos digitais;

2. O "Analisador Léxico" de um compilador típico, isto é, o componente do compilador que divide o texto de entrada em unidades lógicas como identificadores, palavras-chave e pontuações.

3. Software para examinar grandes corpos de texto, como coleções de páginas Web, a fim de encontrar ocorrências de palavras, frases ou outros padrões.

4. Software para verificar sistemas de todos os tipos que têm u número finito de estados destintos, como protocolos de comunicação ou protocolos para troca segura de informações.

Linguagens formais e Autômatos existem para serem reconhecedores de cadeias, no nosso dia a dia estamos mais próximos dos reconhecedores de cadeias do que pensamos, como por exemplo o famoso corretor ortográfico, que é uma aplicação que foi criada para reconhecer cadeias de caracteres, ou falando de algo mais moderno, o tão falado ChatGPT, ele também é um reconhecedor de cadeias.

Caractere

Mas a final o que é um caractere? Nada mais é do que um símbolo qualquer, cada letra do alfabeto romano, cada número é um caractere.
Existe uma quantidade infinita de caractere, e com o poder computacional que temos, é impossível trabalhar com números infinitos de dados, então reduzimos a quantidade de caractere para 256, criando a tabela ASCII.

Alfabeto

O alfabeto é um subconjunto de caracteres da tabela ASCII.
Nós utilizamos um símbolo para representar o alfabeto, o símbolo de somatória.

• Σ ← Significa alfabeto
• Σ = { a, b, c } Aqui nosso alfabeto está sendo representado pelos caracteres a, b, c.
• Σ = { 1, 2, 3 } Aqui estamos representando nosso alfabeto com os caracteres 1, 2 e 3.
• Σ = { 0, 1 } Aqui representamos com 0 e 1.
• Σ ={@,3, , ,/, A, º, } Aqui temos vários símbolos diferentes que juntos representam nosso alfabeto.

Vale ressaltar que o alfabeto é um conjunto e não uma sequência, na realidade a sequência li nem importa, geralmente colocamos em ordem para facilitar a leitura.

Cadeias

Cadeias são uma sequência de caractere, todos eles pertencentes ao alfabeto, se pegarmos nosso caractere e sequencial-los temos uma cadeia de caractere, como muitos conhecem uma "String".
Strings nada mais são do que uma cadeia de caracteres, vamos chamar nossas cadeias de C e seu índice.

• C¹ = aba
• C² = bbaa
• C³ = b

É possível notar que é possível criar uma infinidade de cadeias com nosso alfabeto.

Propriedades das cadeias

Aqui nós temos algumas propriedades para podermos fazer algumas operações, algumas manipulações.

Tamanho | |

O tamanho é a quantidade de caracteres da cadeia representado por | |

• C¹ = aba | C¹ | = 3

• C³ = b | C³ | = 1

Concatenação //

É a fusão de duas ou mais cadeias, ou seja é a concatenação de duas ou mais cadeias de caractere, representado por: //

C¹ = aba

C² = bbaa

A propriedade não é comutativa, se eu alterar a ordem ela altera o resultado.

C¹ // C² = aba // bbaa = ababbaa

C² // C¹ = bbaa // aba = bbaaaba

Cadeia reversa __

É a cadeia invertida, ou seja, ela é escrita de trás pra frente

• C¹ = aba C¹= aba

• C² = bbaa C² = aabb

É colocado um travessão mas não consegui colocar aqui com esse editor de texto.

Elemento Neutro λ

Aqui entra uma das principais propriedades, o elemento neutro ele é uma cadeia sem caractere, onde vamos chamá-lo de "vazio", representado pelo símbolo de lambda, λ.

Não confundir com o caractere de espaço em branco da tabela ASCII na posição 32. O λ é ausência de caractere.
Se eu concatenar ele com qualquer cadeia ele não influencia, por isso chamamos de elemento neutro.

C¹ = λ

C² = aba

C¹ // C² // C¹ = C² = aba

| C¹ | = 0

Fecho

Fecho forma um conjunto gerado a partir de concatenações sucessivas de cadeias com ela mesma até o infinito, ou seja, nós temos uma cadeia, e quando nós criamos um conjunto a partir dessa cadeia, nós chamamos de fecho, o mesmo pode ser fecho positivo, quanto fecho estrela.

• Fecho positivo é representado pelo sinal de mais +
• O fecho estrela é representado pelo sinal de asterisco *

Fecho positivo

Imagine que temos o Σ = { a, b }

Temos a como uma cadeia válida, pois ela pertence ao alfabeto, ao adicionarmos nela o símbolo de mais, ou seja a+ isso vai nos gerar um conjunto formado pelo próprio a e a concatenação de a com ele mesmo.

a+ = {a, aa, aaa, aaaa, aaaaa, … } Isso é possível fazer com qualquer cadeia, podemos colocar o fecho positivo nela para gerar um conjunto infinito.

(ab)+ = {ab, abab, ababab, abababab, …} Como podemos ver nesse caso, o ab está junto dentro dos parênteses, então se repete o que está dentro infinitamente.

a+ b = {ab, aab, aaab, aaaab, aaaaab} Aqui podemos ver que só incrementamos o a pois b é uma constante, ele não possuí um fecho.

Fecho estrela

O fecho estrela é igual ao fecho positivo, exceto por um detalhe, o elemento neutro vai fazer parte do fecho. Onde vamos incluir mais um elemento que é o vazio λ

a* = {λ, a, aa, aaa, aaaa, … }

Estamos incluindo ele no começo só para facilitar a visualização, isso não é uma sequência, é um conjunto, ou seja não precisa está em rodem.

a* b = a* // b = {λ, a, aa, aaa, …} // b

Linguagem

Linguagem que é representada por L, é uma ou mais regras que definem um conjunto de cadeias.

Linguagem é uma regra e as expressões regulares são os reconhecedores de cadeias.

Eu posso criar uma regra qualquer, e isso se chamara de linguagem, como por exemplo: Digamos que nós temos o Σ = { a, b } então todas as cadeias que começam com a, serão válidas no meu sistema.

Ou seja eu criei uma regra, que diz que as cadeias só serão válidas no meu sistema, as cadeias que iniciam com o caractere a. **L¹ = {a, ab, aa, aaa, abab, aabaabbb, … }

Vamos criar uma regra que diz, só serão válidas no nosso sistema, as cadeias que terminam em b

L² = {ab, b, bbb, aaab, abab, abbabbb, ...} Então é isso, linguagem são regras, e cadeias válidas são aquelas que seguem a regra.

Poder

Poder quantidade de cadeia que uma linguagem reconhece

O poder de uma linguagem é o conjunto de todos os elemento válidos de uma linguagem. Geralmente é infinito, como por exemplo, as cadeias que começam com a, podemos perceber que são infinitas as possiblidades. Para entender melhor esse conceito de poder, vamos supor que nós temos 3 linguagens:

1. Todas as cadeias que começam com a, L¹ = {a, ab, aab, abba, aaba, … }
2. Todas as cadeias que terminam em b, L² = { b, ab, aab, babbb, aaabab, … }
3. Todas as cadeias que começam em a e terminam em b: L³ = {ab, aab, abab, abbb, ... }

Como podemos perceber o 1º e o 2º possuem mais cadeias válidas que o 3º pois todas as cadeias que estão no 3º estão dentro do 1º e do 2º, mas não o contrário.

Então podemos sim dizer que uma linguagem tem mais poder que a outra, mesmo ambas sendo infinitas. Pois a quantidade de cadeias válidas de uma linguagem é maior que a outra, mesmo que matematicamente elas sejam equivalentes, pois são infinitas.

Propriedade das linguagens

Tomando como base as linguagens anteriores, vamos vez as propriedades das linguagens

L¹ = { a, ab, aab, aa, aaa, abbaa, aababa, … } ,todas que começam com a.

L² = { b, ab, bbb, bb, abb, abbab, babab, … } ,todas que terminam em b.

1. União ∪ OU

Então nesse conjunto união nós teremos tudo que está nos 2 conjuntos de L¹ e L²

Em linguagens de programação é o operador “OR” ou “OU”

Exemplo: L¹ U L² = {a, ab, aab, aa, aaa, abbaa, aababa,b, bbb, bb, abb, abbab, babab, … }

2. Intersecção ∩ E

É tudo que está em ambos os conjuntos, ou seja, só cadeias que começam com a, e ao mesmo tempo terminam em b. Nas linguagens de programação é operador “AND” ou “E”.

Exemplo: L¹ ∩ L² = {ab, abab, aabb, ababab, … }

3. Não ~

Ou seja ele é o operador que inverte, em linguagens de programação ele é o “NOT” ou “Não”.

Exemplo: ~L¹ = { λ, b, ba, bab, bb, bbb, baa, … } todos que não começam em a.

4. Diferença —

Essa propriedade quer dizer que é um conjunto menos o outro, vamos imaginar L¹ - L² ou seja nós vamos tirar de L¹ o que tiver em L².

Se L¹ é todos que começam com a, e L² é todos que terminam em b, então eu vou remover de L¹ todos que terminam em b

L¹ - L² = { a, aba, aa, aabaaba, aabbbbbaba, … }

Expressões regulares

Expressões regulares são nosso primeiro reconhecedor de cadeias, como mencionado anteriormente, linguagens são regras, e expressões regulares vão obedecer essas regras para que seja possível validar cadeias de caracteres.

Expressão regular, é escrever a linguagem por meio de alguns elementos específicos, então quando eu for escrever uma linguagem, não vamos escrever “começa com a”, nós iremos escrever uma expressão que represente isso, que represente tudo que comece com a.

Expressões regulares são representação de uma linguagem por meio de:

• Elementos do alfabeto;
• Parênteses;
• Propriedades da cadeia ( Elemento Neutro e Fecho );
• Propriedades da linguagem ( União e Não)

---

Vejamos exemplos de expressões considerando Σ = { a, b }

• L = { a, aa, aaa, aaaa, … }
  • L = a+
• L = { ab, aab, aaab, aaaab, … }
  • L = a+b
• L = {a, ba, bba, bbba, … }
  • L = b* a
• L = { a, aa, ab, aab, abb, aabb, aaab, abbb, aabbb, … }
  • L = a+b*
• L = { a, aab, aabab, aababab, aabababab, … }
  • L = a (ab)*
  • L = (a+b*)+

Exemplos de expressões regulares

L = Todas as cadeias que começam em “a“

• L = (a+b*)+
  L = Todas que terminam em “b”
• L = (a*b+)+
  L = Todas as cadeias válidas no alfabeto { a, b }
• L = (a* b*)*

Nós chamamos essa expressão L = (a* b*)* de “qualquer coisa” pois dado o alfabeto {a, b} ele pode assumir qualquer valor, ou seja pode ser qualquer cadeia desse alfabeto.

Reescrevendo expressões regulares anteriores

L = Todas que começam em “a”

• L = a(ab)*

L = Todas que terminam em “b”

• L = (a* b*)* b

L = Todas que possuam um par de “a” juntos

Exemplos de cadeias válidas: { **aa**, b**aa**, **aa**b, ababb**aa**bbab, abab**aa**b }

• (ab)* aa (ab)*

Como podemos perceber no exemplo anterior não colocamos fecho positivo pois na questão pede explicitamente um par de a juntos, e como é constante então não colocamos o fecho positivo pois se colocássemos estaríamos invalidando a cadeia, pois com o fechoele poderia ser um valor impar.

Usando a propriedade da linguagem

Σ = { a, b }

L = Todas que tenham pelo menos 2 elementos.

• L = (ab)* aa U (ab)* bb U (ab)* ab U (ab)* ba

L = Todas que não terminam em “b”

• L = (ab)*a U λ

L = Todas que possuam exatamente 3 “b”

• L = a* b a* b a* b a*

L = Todas que tenham uma quantidade Par de “a”

• L = (b* a b* a b*)*

L = Todas que tenham uma quantidade Impar de “a”

• ~(b* a b* a b*)*

Autômatos Finitos

O que temos no autômato finito

Nós temos dois elementos importantes.

Estado

Estado é a descrição do sistema em um determinado instante, estado também poderia ser uma “tela”.

Transição

Transição é uma mudança de estado, as transições são as setas, que no caso do nosso dígrafo, são as arestas.

Podemos ter 3 tipos de transições:

1. De usuário: provocada por uma ação do usuário;
2. Espontâneas: Provocada por uma ação mecânica, do sistema.
3. Instantânea: Provocada apenas uma vez, e acontece na inicialização do sistema

O que é um Autômato Finito?

É uma quíntupla, formada por:

• Q: Conjunto finito de estados;
• Σ: Alfabeto;
• S⁰: Estado Inicial. S⁰ ∈ Q e é único em todo o autômato;
• F: Conjunto de estado finais. F ⊆ Q. F são os estados de aceitação de uma cadeia;
• δ: Função de transição Q x Σ → Q.

Principal objetivo

O principal objetivo dos autômatos é a validação de cadeias. Para uma cadeia ser válida, ela precisa fazer transições que iniciem no estado inicial do autômato e terminem em algum estado final do mesmo. Caso a cadeia termine em um estado dito não final, a cadeia é considerada invalida.

Ele vai testar as cadeias, pegando como exemplo a questão que a gente fez, “Contenham um par de a” o autômato finito, vai receber essa cadeia e vai testar se ela contem ou não, assim definindo se é uma cadeia válida ou inválida.

Uma grande utilidade do autômato é fazer um compilador, pois compilador é isso, nós temos uma cadeia de caracteres, que é o algoritmo, e ele vai verificar se aqueles caracteres são cadeias válidas.

Convenções

As convenções usadas aqui são usadas por muitos autores, mas não por todos, portanto, em algumas literaturas, símbolos deferentes podem ser encontrados, sem que isso altere o conceito do mesmo.

• Nome dos estados, será sempre a letra q, e serão diferenciados por um índice.
  • q⁰, q¹, q², q³ … qn
• q⁰ será sempre o estado inicial.
• Os estados serão representados por um círculo, com seu nome no interior.
  
• O estado inicial será demarcado com uma seta que vem do “nada” e e apontando para o estado inicial.
  
• Os estados finais serão demarcados com um círculo em seu interior.
  
• Duas transições diferentes, partindo de uma mesma origem e chegando a um mesmo destino, poderão ser representados, com uma seta única, e seus nomes serão separados por vírgula.
  

Determinismo

O autômato finito é dito Determinístico se, e somente se, para cada elemento do alfabeto exista uma, e apenas uma transição de saída, de cada estado pertencente ao autômato, ou seja, um mesmo elemento do alfabeto não pode ter duas ou mais transições de saída de um mesmo estado, obrigatoriamente, deve ter uma saída do mesmo.

Imagine que estamos na nossa tela inicial do programa e temos 2 saídas ao digitar 1, para onde o programa deveria seguir?

Um autômato finito determinístico não pode ter transições espontâneas. Ou seja não pode ter nenhuma transição vazia, ou dos elementos que não seja do alfabeto.

Construção de autômatos finitos

Para construir autômatos finitos, nós precisamos obedecer 2 regras.

1. A regra da cadeia mínima.
2. A regra da transição.

Vale ressaltar que se, somente se ao perceber que não teria como gerar a cadeia mínima, ai nós pegamos o resultado errado, e utilizamos a regra da transição, para transforma-los em um estado certo.

Cadeia mínima

Passo 1 - Verificar se os elementos que compõe a linguagem fazem parte do alfabeto;

Passo 2 - Isolar a cadeia mínima.

Para ver a cadeia mínima é fácil, só precisamos remover o fecho estrela, e o que sobrar é a cadeia mínima.

Passo 3 - Escrever uma sequência do estado inicial a um estado final, com a cadeia mínima (esqueleto).

Aqui para a construção do esqueleto, nós precisamos da cadeia mínima, supondo que a cadeia mínima tem 5 caracteres, então nosso esqueleto tem 6 estados. q0, q1, q2, q3, q4, q5

Passo 4 - Tornar o autômato determinístico, usando os lemas e o estado morto quando necessários.

Temos que ter para cada caractere da nossa linguagem, 1 saída válida.

Exemplo

Σ = {0,1} L = 01+

Passo 1 - Todos os elementos que compõe a linguagem fazem parte do alfabeto.

Passo 2 - A cadeia mínima é 01

Passo 3 - montar o esqueleto

Passo 4 - aplicar o determinismo, onde temos que ter uma saída em cada estado, para cada caractere do alfabeto, incluindo o morto.

Considerações finais

Espero ter te estigado pelo menos um pouco ao ponto de fazer você ir pesquisar mais sobre o tema, deu muito trabalho escrever esse post, espero de coração que ajude alguém, qualquer dúvida só deixar seu comentário a baixo. ❤️