Para um grande conjunto de problemas é mais informativo ter uma estimativa em média do que a mesma estimativa para o pior caso. No entanto a forma usual para obter estimativas médias é através da recolha de dados obtidos por experimentação sendo o resultado sempre uma aproximação por muito significativa que a amostragem utilizada seja.
Na campo das linguagens formais, o tamanho do menor modelo que representa uma linguagem é uma boa medida da sua complexidade. No estudo do efeito das diversas operações sobre esta medida de complexidade assistiu-se a um crescente interesse nas últimas décadas, testemunho da importância que adquiriram as suas aplicações, da verificação formal de programas, passando pelo reconhecimento de padrões até ao processamento de voz. Mas para além do estudo desta complexidade, no pior caso, importa obter resultados em média, que não obstante serem muito mais difíceis, têm uma muito maior importância prática. Nesta introdução, para além da apresentação dos conceitos fundamentais envolvidos, será mostrado como as técnicas da Combinatória Analítica podem contribuir para resolver alguns problemas difíceis nesta área, sem qualquer recurso à experimentação. |