4
$\begingroup$

I was reading the venerable "How to Find or Validate an Email Address [using Regex]", and I came across the following statement at the bottom of the page:

[A] true regular language cannot enforce a length limit and disallow consecutive hyphens at the same time.

This seems wrong to me.

I feel like if the length of a string is bounded ahead of time, you should be able to write a DFA which processes pretty much any rule on the input string, as you can just create $n$ states from the most recent states, where $n$ is the number of letters in the alphabet, repeating for the maximal length of the input string?

If this reasoning is wrong, can someone point me in the right direction?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

You are not wrong. In fact, any finite language $L$ over a finite alphabet $\Sigma$ is regular. If $L$ is finite, there must be an integer $d$ such that for all $x \in L$ it holds that $|x| \le d$. Let $|\Sigma| = s$ and construct a complete $s$-ary tree of depth $d$, where each edge from a node to one of its children is a transition associated to some $c \in \Sigma$.

We can see that such a tree enumerates all the strings over $\Sigma$ of length at most $d$; this means that each string of $L$ must correspond to some node of the tree. Marking as an accepting state every such node yields a DFA for $L$.

Notice that the resulting DFA may be very ugly, but it's a valid DFA nonetheless, and that is sufficient if we are only concerned with regularity.

Improve this answer
$\endgroup$
0
$\begingroup$

Yeah, that claim looks bogus to me. Regular languages are closed under intersection. The set of all words of length at most $k$ is regular; the set of all words with no consecutive hyphens is regular; so their intersection is regular. Every regular language can be matched by a regular expression.

That said, the resulting regular expression might be awfully ugly... Also, it's not clear whether it is all that important to reject email addresses with a domain name that is longer than 63 characters in any case.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The 63-character limit is probably related to limitations imposed by some of the underlying protocols. Still, it makes no difference as far as regularity is concerned. $\endgroup$
    – quicksort
    Commented Feb 8, 2017 at 21:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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