3
$\begingroup$

What is the definition for the length of a regular expression? This question might sound simple, yet I cannot find a definition. Do I only count letters from the alphabet? Do * and $\cup$ count? For example: let r = $(ab)^*\cup$ $a$. What is $|r|$?

$\endgroup$

2 Answers 2

7
$\begingroup$

I assume, you want to define the length of a regular expression such that you can make statements like: The Thompson construction creates an NFA from a regular expression with a number of states that is linear in the length of the expression.

In that case, it is crucial to include operator symbols, otherwise the above statement would not be true for the expression $a^{\ast\ast\ast\ast\ast\cdots\ast}$.

However, if you preprocess expressions such that there are no nested Kleene stars or trailing $\varepsilon$s, then it does not matter much, as then the different definitions only differ by a constant factor. A short write up on this which I think is quite good, you can find in this paper

¹ Keith Ellul, Bryan Krawetz, Jeffrey Shallit, and Ming-wei Wang. Regular Expressions: New Results and Open Problems. Journal of Automata, Languages and Combinatorics, 10(4) 2005

$\endgroup$
7
$\begingroup$

There are two conventions I know of.

One is defining the size of a regular expression as the size of the binary tree representing the expression. As such, the size of the expression is the total number of symbols in the expression, counting $\emptyset$, $a\in \Sigma$, $*$, $|$ and $\cdot$ (parentheses are not counted).

An other definition removes the $\cdot$ (concatenation product) from being counted. This is somewhat usefull in the Thompson's construction: the constructed NFA for $e$ has at most $2|e|$ states (this is due to the fact that the concatenation symbol does not increase the size of the automaton).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.