Metodo Bolha

LINGUAGENS FORMAIS (REVISÃO)
Os estudos sobre linguagens formais iniciaram-se na década de 50 com o objetivo de definir matematicamente as estruturas das linguagens naturais. No entanto, verificou-se que a teoria desenvolvida aplicava-se ao estudo das linguagens de programação.
A teoria de linguagens formais engloba, basicamente, o estudo das características, propriedades e aplicações das linguagens formais, bem com a forma de representação da estrutura (sintaxe) e determinação do significado (semântica) das sentenças das linguagens. A importância desta teoria é dupla: tanto apoia outros aspectos teóricos da teoria da computação, tais como decibilidade, computabilidade, complexidade, etc. como fundamenta diversas aplicações computacionais, como por exemplo processamento de linguagens, reconhecimento de padrões, modelagem de sistemas, etc. Mas, o que é uma linguagem?

Uma linguagem é uma forma de comunicação, usada por sujeitos de uma determinada comunidade;
Uma linguagem é o conjunto de SÍMBOLOS e REGRAS para combinar esses símbolos em sentenças sintaticamente corretas.
"uma linguagem é formal quando pode ser representada através de um sistema com sustentação matemática".

Assim sendo, são necessários conceitos matemáticos para o estudo das linguagens formais. Símbolo
Um símbolo é uma entidade abstrata básica sem definição formal. São exemplos de símbolos as letras, os dígitos, etc. Símbolos são ordenáveis lexicograficamente e, portanto, podem ser comparados quanto à igualdade ou precedência. Por exemplo, tomando as letras dos alfabetos, tem-se a ordenação A < B < C < ... < Z. A principal utilidade dos símbolos está na possibilidade de usá-los como elementos atômicos em definições de linguagens.

Sentença (ou palavra)
Uma sentença (ou palavra) é uma seqüência finita de símbolos. Sejam P, R, I, M, e A símbolos, então PRIMA é uma sentença. As sentenças vazias, representadas por , é uma sentença constituída por nenhum símbolo.

Tamanho de uma