# regular expression in license plates

I'm trying to write a regular expression for some particular license plates. They consist of one up to three capital letters, a hyphen, one up to two capitol letters and one up to four numbers. The license plate should not exceed the 8 symbols.

Example: AA-AA123

What I have until now is the following:

because there has to be at least one letter before the hyphen, I have this expression for the first letter: $$P = (A\cup B \cup...\cup Z)$$

For the second letter: $$D = (A\cup B \cup...\cup Z\cup empty)$$ empty indicates the possibility that there could not be a letter.

For the numbers is basically almost the same procedure: $$E = (1\cup 2 \cup...\cup 9)$$ $$F = (1\cup 2 \cup...\cup 9 \cup empty)$$

now for my explicit expression I think the answer would be: $$K= PDD^* - PDEF^*F^*$$

but I'm not quite sure. I think this means I have 8 symbols, at least one letter before the hyphen but I could have up to three, the hyphen (that is a must), at least one letter after the hyphen but up to two and at least one number but I could have up to 4.

Something tells me I have something wrong here, I'm still new in the regular expressions world and I appreciate any help I could get in advance.

• Anything with a star in it will accept strings of arbitrary length but your specification says you shuold reject anything more than eight characters. May 1 '14 at 11:49

As David Richerby pointed out $D^*$ will accept an arbitrary number of letters (including none). If I'm not mistaken you need to take all possible options to achieve not having more than 8 characters. $$K = ( PDD-PDEF ) \cup (PDD-PEFF) \cup (PD-PDEFF) \cup (PD-PEFFF) \cup (P-PDEFFF)$$ This assumes the hyphen is one of the 8 letters and thus does not allow more than 8 letters. Less letters are allowed because of your definitions of $F$ and $D$ including the empty word $\varepsilon$.

EDIT: added missing cases from commenter.

• Your definition is incomplete as there can be up to four numbers, so something like (PHPDEFFF) is also accepted as a valid string. I use H for {-} because '-' just confuses me. May 1 '14 at 16:37
• @Tushar: Thanks for the comment. I added the missing cases. May 1 '14 at 16:40

A straightforward answer is that it must match the regexp $P\{1,3\}-P\{1,2\}E\{1,4\}$ and must be exactly 8 characters long. If I was implementing this in code, that's what I would do: I would check that it matches the former regexp, and check that its length is 8.

Note on notation: $P\{1,3\}$ means one to three repetitions of $P$. Of course, you can remove this standard notation using standard methods: e.g., $P\{1,3\}$ is equivalent to $(P|PP|PPP)$, and so on. Thus, the regexp I gave earlier is equivalent to $(P|PP|PPP)-(P|PP)(E|EE|EEE|EEEE)$.

If you insist on a single regexp that checks everything, without a separate check that the license plate is 8 characters long, you could re-express the requirement that this must be exactly 8 characters long as the regexp $(P|E)\{8\}$, so we want something that matches both $P\{1,3\}-P\{1,2\}E\{1,4\}$ and $(P|E)\{8\}$. Since regular languages are closed under intersection, you can derive a single regular expression for their intersection using standard techniques.

Yet another way to approach this is to build up a finite-state automaton to recognize such license plates, then convert it to a regexp. Your individual constraints can be expressed in a straightforward way as a non-deterministic finite-state automaton (NFA), and then there are standard ways to convert a NFA to a regexp.