Partial Derivative Automaton for Regular Expressions with Shuffle

2015/03/01 by Broda, Sabine, Machiavelo, António, Moreira, Nelma +1
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.1503.00279

Abstract

We generalize the partial derivative automaton to regular expressions with shuffle and study its size in the worst and in the average case. The number of states of the partial derivative automata is in the worst case at most 2^m, where m is the number of letters in the expression, while asymptotically and on average it is no more than (4/3)^m.

Related

• On The Space Complexity of Partial Derivatives of Regular Expressions with Shuffle
• Partial Derivatives for Context-Free Languages: From μ-Regular Expressions to Pushdown Automata
• On the Uniform Distribution of Regular Expressions
• Regular languages, derivatives and finite automata
• Reordering Derivatives of Trace Closures of Regular Languages (Full Version)