# Regular Expression for the language that requires one symbol to occur at least once

I am trying to figure out the simplest way to do this using a regular expression.

• Three symbols a, b, c.
• The sequence length is unlimited, i.e. *.
• The symbol a must be somewhere in the sequence at least once, but can appear more than once.
• The sequence may have only a.

More formally, $\{ w \in \{a,b,c\}^* ~|~ \#_a(w)\ge 1 \}$, where $\#_a(w)$ is the number of $a$s in $w$.

The best I get is

$( ( b \mid c )^*\, a\, ( b \mid c )^* )^+$

Is that the simplest way?

• You ask for EBNF, but you give a regular expression. What is it you want? Also, what does "The sequence can have only a" mean; one one of something (what?) or only symbols $a$? – Raphael Apr 4 '12 at 5:54
• It is actualy part of a grammar, thus the EBNF. sepp2k hit the nail on the head with his answer. – Guy Coder Apr 4 '12 at 11:00

The simplest regular expression I can think of for this is $\left(a \mid b \mid c\right)^* a \left(a \mid b \mid c\right)^*$. This is simpler than yours by the following measures of complexity:

• It contains less nesting (and fewer parentheses in general)
• It contains fewer quantifiers
• @GuyCoder I meant the number of characters in the regex. Mine has 17, yours has 20. – sepp2k Apr 4 '12 at 2:04
• @sepp2k: Counting superfluous parentheses is not fair. – Raphael Apr 4 '12 at 10:20
• This is simpler because it is nested only to depth one, which makes reasoning about it much easier than if the depth were two or more. In fact, I vote this the simplest and clearest possible. – David Lewis Apr 4 '12 at 10:53
• @Raphael I don't need to count superfluous parentheses to have fewer of them. His expression has 3 pairs of non-superfluous parentheses with a nesting-depth of 2. Mine has 2 pairs and a nesting depth of 1. – sepp2k Apr 4 '12 at 12:58

As the expression is to be part of a parser (i.e. should be efficiently checkable), it might be a good idea to make the regular expression unambiguous:

$\qquad \displaystyle (b \mid c)^*\, a\, (a \mid b \mid c)^*$

describes the same language but avoids ambiguity by distinguishing the first $a$ in a matching word. Wether this has an impact depends on the way your parser generator works.

This is the same written as diagram, with the token names the OP uses: Image by Guy Coder.

• Also, it is just that tiny bit shorter than Sepp's. :] – Raphael Apr 4 '12 at 16:32
• @GuyCoder: This one is unambiguous. I guess your problem lies elsewhere? – Raphael Apr 4 '12 at 17:23