OK, so you were pretty close:

while (<DATA>) {
  chomp;
  print "$_ ";
  if (/^[a-z][a-z \-]*/) {
    print "OK\n";
  } else {
    print "NOT OK\n";
  }
}

__DATA__
sdlfj
dsfj-dlf
dish dslf
dsf-ldj sdf
-
  
*$)#&%_!@...
[download]

-- Dan