Introdução

Em suma, na maioria das graduações de Sistemas de Informação e Ciência da Computação, temos uma matéria/grade sobre linguagens formais. Mas o que de fato seria "Linguagens Formais", e qual seria seu propósito?

Para respondermos isso, precisamos ter conhecimento básico do nosso ensino Fundamental e Médio sobre português. Sim, imaginou que codar seria ignorar totalmente seu aprendizado em português? Achou errado, meu amigo dev.

Na Teoria de Linguagens Formais, temos como definição sobre linguagem de modo formal:

"É um conjunto de elementos (símbolos) e um conjunto de métodos (regras) para combinar estes elementos, usado e entendido por uma determinada comunidade". Resumindo, sintaxe e semântica do seu querido ensino médio.

Com isso esclarecido, podemos dizer que "linguagens formais" são mecanismos formais para representação e especificação de linguagens, baseados na chamada teoria da computação.

Gramática

Para cada Linguagem Formal, temos uma gramática também, e cada etapa dessa mesma gramática, digamos que o poder computacional aumenta também, dado pelo formalismo que Avram Noam Chomsky em sua teoria hierárquica.

Mas tudo bem, como que algo de linguagem e gramática consegue aumentar poder computacional de algo, como se valida tal linguagem?

Suponhamos que temos uma linguagem que contem em seu alfabeto {a,b}, e nessa linguagem podemos aceitar TUDO, então teremos como exemplo palavras:

Tudo começa com qualquer uma das letras desse alfabeto, ou termina de qualquer jeito. Esse tipo de linguagem, apesar de ser simples, é uma linguagem. Mas okay, vamos limitar: UMA LINGUAGEM QUE SÓ ACEITA FINAL COM (ab):

Agora temos um problema mais recorrente, as Linguagens Formais, mostrando ali que uma linguagem só ACEITA se tiver (ab) no final, fazendo assim, uma linguagem que valida se aquela palavra é válida ou não na linguagem.

Exemplo na sua Linguagem de Programção

Mas Gui, para que serve tudo isso então? Simples, sua linguagem de programação favorita não acusa erro se você errar comandos sintáticos como IF/WHILE/FOR ? Isto é, errar os nomes como, "UF" invés de "IF", ou até mesmo esquecer uma letra do comando como "WHIL" esquecendo "E" do comando WHILE.

ISSO TUDO É O QUE SUA LINGUAGEM FAZ, SEGUINDO AS ORIENTAÇÕES DE UMA LINGUAGEM FORMAL!!!!

E para mais funcionalidades como Sintaxe, Semântica e até mesmo dupla validação (famoso fecha colchetes ou chaves), a Linguagem Formal consegue validar, contudo, temos que aumentar seu poder computacional para conseguirmos validar esse tipo de problema.

Hierarquia de Chomsky

Como disse acima, temos passos que aumentam o poder computacional, e dentre eles, são outras validações. Como exemplo acima, é uma linguagem REGULAR, lembre-se disso, a validação da sintaxe é feita por ele, e é a base da hierarquia, onde o poder computacional é o menor que tem.

Se pularmos mais uma etapa, iremos chegar à Gramática Livre de Contexto, que faz validações de duplo balanceamento. Por exemplo:

Palavras que contêm mesma quantidade de A e B.

E como funciona? Esse tipo de linguagem contém praticamente UMA PILHA de validação. Por isso que aumenta o poder computacional, pois você realmente coloca algo a "mais" no mecanismo de validação.

Isso acontece na sua linguagem favorita, ela contém uma GLC (gramática livre de contexto) que valida quantos { } e ( ) que você tem. Até mesmo seus if e elses.

Não pense que acabou, pois ainda temos mais linguagens acima dessa, e alguns chegam ao poder computacional INFINITO. E para ter:

• Linguagem Recursiva (Gramática Sensível ao Contexto)
• Linguagem Recursivamente Enumerável (Gramática Irrestrita)

As Linguagens Recursivas são muito usadas como as Máquinas de Turing, com poder computacional ainda maior, e por fim, as Linguagens Recursivamente Enumeráveis, que são conceitos abstratos sobre MEMÓRIA INFINITA, e bom, se temos memória infinita, temos poder computacional praticamente infinita também.

Máquinas de Aceitação.

Além de termos linguagens e gramáticas, temos as máquinas que aceitam ou não determinadas palavras para aquela linguagem designada. Para podermos exemplificar, as máquinas são uma forma visual e gráfica de como decorre em "estados" a linguagem, e nela, mostramos que a linguagem irá parar em um estado que consideramos final.

Exemplo de uma máquina de autômato finito.

L = palavras sobre {a, b} que começam e terminam com a e possuem pelo menos um b.

Sabendo que temos (qo) como estado inicial (símbolo de triângulo), e (q3) como estado final (com um círculo adentro). Com uma palavra:

Sendo (q3) um estado final, podemos parar por aqui e falar com propriedade que essa palavra é ACEITA na linguagem acima. Agora vamos a outro exemplo.

Sendo q2 é um estado NÃO FINAL, podemos afirmar que essa palavra (abb) NÃO SERÁ ACEITA.

Conclusão.

Temos então um resumo bem breve sobre Linguagens Formais e também seus autômatos. Parece ser algo simples e irrelevante, contudo, conceitos abstratos e teóricos deixam-nos ter maior sabedoria e discernimento sobre como realmente funcionam as tecnologias que possuímos e utilizamos.
As Linguagens Formais mostram um mundo introdutório de como funciona uma linguagem de programação de forma abstrata, e até mesmo o funcionamento de um interpretador/compilador. Espero ter conseguido introduzir esse belo mundo sobre linguagens formais, nos vemos na próxima.

Referências

Ricardo Terra
Apostila Linguagens Formais e Autômatos
Apostila Teórica, 2024

F. Blauth Menezes.
Linguagens formais e autômatos, volume 3.
Bookman, 6 edition, 2011.

J. E. Hopcroft and J. D. Ullman.
Formal languages and their relation to automata.
Addison-Wesley, 1969.

J. E. Hopcroft and J. D. Ullman.
Introduction to Automata Theory, Languages, and Computation.
Addison-Wesley, 1979.

M. Sipser.
Introdução à Teoria da Computação
Thompson, 2007.