Take a look at the following code sample.
From what I understood, only str2, str3 and str6 should match.
About the regexp:
- Note I am not using =~. I am saying 'if it does not match'
- Search for two words followed by either 'to' or 'from' but make sure it is not followed by a word char or it is the end of string.

#!/usr/bin/perl -w

my $str1 = "train times tomorrow xyz";
my $str2 = "train times to xyz";
my $str3 = "train times from xyz";
my $str4 = "train times defrom xyz";
my $str5 = "train times fromar xyz";
my $str6 = "train times from";
my $str7 = "train from somewhere";

if($str1 !~ /^(\w+)?\s+(\w+)?\s+(to|from)([^\w]|\z)/) {
  print "does not match. Now we can do something\n";
}
[download]