Pensando Sobre Matemática #8

Esse post é melhor visualizado na versão para web com javascript ativado!

Mais um patrocínio gratuito da galera do MathJax, te auxiliando a exibir conteúdo matemático na web.

Hoje vamos falar um pouco mais sobre linguagens.

Mas linguagem? O que diabos isso tem a ver com matemática?

Bom vamos começar pelo fato de que a matemática é uma linguagem, e não uma ciência. As ciências se valem da linguagem matemática pois ela é muito mais sucinta para exprimir aquilo que os cientistas querem, que são basicamente medidas e relacionamentos entre elas. Quando Newton falou: $$F=m\cdot a$$ Ele só quis dizer que a força resultante em um objeto é diretamente proporcional ao produto de sua massa e sua aceleração. Só que de uma forma extremamente sucinta. Diga-se de passagem a expressão matemática ali nos diz até como a proporcionalidade entre as dimensões se comporta. Então para isso a matemática é extremamente poderosa.

Mas saibam que o operador de igualdade que relaciona duas expressões surgiu apenas no século dezesseis. Imagina como devia ser um inferno pra Euclides, Aristóteles, Arquimedes, Pitágoras, e aquela galera toda pra poder fazer matemática!

Isso tudo evoluiu. E uma coisa nova que surgiu, foi um jeito completamente diferente de se tratar linguagens. Surgiu no início do século vinte, com a parceira de quatro caras bastante influentes. Obviamente deve ter tido mais gente, mas esses quatro tiveram maior peso no que diz respeito a linguagens e a teoria da computabilidade. São eles: Alan Turing, Alonzo Church, Stephen Kleene e Emil Post. Provavelmente já haviam estudos sendo feito antes pelos irmãos Bernoulli(esses caras estão em todas!) e Ada Lovelace.

Qual é a brincadeira aqui? É um jeito até relativamente curioso de se pensar. Se você exclui os acentos, você pode dizer que todas as palavras podem ser escritas usando as vinte e seis letras do alfabeto. Agora só falta a gente dizer exatamente o que é uma palavra, o que se tornou relativamente fácil desde que a gente começou a utilizar notação posicional para os números. Se os número são um bando de algarismos posicionados uns ao lado dos outros, com uma ordem pra dizer quem é o mais significativo, palavras são letras dispostas ordenadamente umas ao lado das outras!

Daí a gente chega a uma definição matemática de alfabeto. É só um conjunto de símbolos! Um conjunto eu suponho que vocês já saibam o que é. Por exemplo: $$A=\{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z\}$$ Como todo bom conjunto, não há elementos, repetidos. Diferentemente da palavra, que é uma sequência ordenada de símbolos do alfabeto. Note que até um símbolo sozinho pode significar uma palavra. Daí você pode ter conjuntos de palavras e pode até fazer operações com elas. Por exemplo vamos pegar dois conjuntos simples de palavras: $$P_0=\left\{\mathrm{de}\right\}$$ $$P_1=\{\mathrm{va},\mathrm{ve}\}$$ E você opera sobre eles! Similarmente a números e conjuntos! $$P_0\bigcup P_1=\{\mathrm{de},\mathrm{va},\mathrm{ve}\}$$ $$P_0\bigcap P_1=\left\{\varnothing \right\}$$ $$P_0+P_1=\{\mathrm{deva},\mathrm{deve}\}$$ Note aqui que isso não é uma adição e sim uma concatenação. Logo esse operador não é comutativo! Ou seja: $$P_1+P_0=\{\mathrm{vade},\mathrm{vede}\}$$ Isso tudo já é bastante coisa e já da pra manipular bastante algumas linguagens, porém os caras foram ainda mais fundo e criaram um operador sobre um único conjunto que é específico para o estudo de linguagens. A estrela de Kleene. Que nada mais é do que um "*", mas o efeito dela é fazer concatenações recursivas do conjunto com ele mesmo. pra exemplificar isso a gente vai precisar de um alfabeto menor. Vejamos esse alfabeto aqui: $$\Sigma =\{a,b\}$$ Muito mais simples. Agora nós vamos pegar um conjunto de palavras, dentro desse alfabeto. A gente pode começar com: $$W=\{a,b\}$$ Daí você começa a unir as concatenações do conjunto com ele mesmo. Se eu concateno W com W eu tenho: $$W_2=W+W=\{\mathrm{aa},\mathrm{ab},\mathrm{ba},\mathrm{bb}\}$$ Mas a estrela de Kleene vai além! $$W_3=W+W_2=\{\mathrm{aaa},\mathrm{aab},\mathrm{aba},\mathrm{abb},\mathrm{baa},\mathrm{bab},\mathrm{bba},\mathrm{bbb}\}$$ Simplificando: $$W_{i+1}=W+W_i$$ E agora você junta tudo: $$W_u=\bigcup _{i>1}{W}_i$$ $$W*=W\bigcup W_u$$ Algumas pessoas definem a estrela de Kleene junto com uma definição a mais que é a da palavra vazia. A palavra vazia é uma palavra que não contém nenhuma letra no alfabeto. Ela não é particularmente útil aqui, mas é muito interessante quando você define gramáticas.

Essa forma de entender as palavras é o que dá as bases da computação, e fez surgir uma série de problemas muito curiosos a respeito de computação e decisão. Vale a pena dar uma explorada sobre essa forma de enxergar as coisas.

Por hoje é só!