0
$\begingroup$

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.

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

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Tushar May 1 '14 at 16:37
  • $\begingroup$ @Tushar: Thanks for the comment. I added the missing cases. $\endgroup$ – Artemis May 1 '14 at 16:40
0
$\begingroup$

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.

$\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.