Why is gene prediction in eukaryotes such a difficult task? Every gene starts with a codon and the non coding regions in between a coding region also has some specific base sequence(which are used by enzymes to recognize non coding regions during splicing). A computer program could simply search for start codon and then for stop codon. In between it could also search for those non coding regions since they start with specific base sequences. Why does gene finding need such complex things such as HMM?
The main problem is that while most of the things you describe are necessary to have a protein coding gene (introns, the non-coding regions within a coding region, aren't actually per se, even though they're common), they are not sufficient. Additionally there are also genes for non-coding RNAs (including tRNA and rRNA), which obviously don't have a 'coding region' (and also usually no introns).
In order to classify something as a functional gene we usually require that is actually made into (at least) RNA, which requires regulatory sequences that lead to transcription of the gene, these are called promotors. In eukaryotes there are many different promotor sequences, so its very hard to predict them computationally, additionally there are evolutionary remnants in our genomes, which are called pseudo-genes, and while they still have the general structure of a gene, they are not actively used any more.