Technical Report: DCC-2012-05

An Introduction to Desriptional Complexity of Regular Languages through Analytic Combinatorics

Sabine Broda, Nelma Moreira, Rogério Reis

DCC-FC & CMUP, Universidade do Porto
e-mail: {sbb,nam,rvr}@dcc.fc.up.pt

António Machiavelo

DM-FC & CMUP, Universidade do Porto
e-mail: ajmachia@fc.up.pt
July 2012

Abstract

Nowadays, an increasing attention is being given to the study of the descriptional complexity on the average case. Although the underlying theory for such a study seems intimidating, one can obtain interesting results in this area without too much effort. In this gentle introduction we take the reader on a journey through the basic analytical tools of that theory, giving some illustrative examples using regular expressions. We finalize with some new asymptotic average case results for several epsilon-NFA constructions, presented in a unified framework.