diff --git a/src/regexp_nfa.c b/src/regexp_nfa.c
index 69370ac..6a80bcc 100644
--- a/src/regexp_nfa.c
+++ b/src/regexp_nfa.c
@@ -865,14 +865,10 @@
 		 * pattern -- regardless of whether or not it makes sense. */
 		case '^':
 		    EMIT(NFA_BOF);
-		    /* TODO: Not yet supported */
-		    return FAIL;
 		    break;
 
 		case '$':
 		    EMIT(NFA_EOF);
-		    /* TODO: Not yet supported */
-		    return FAIL;
 		    break;
 
 		case '#':
@@ -1780,6 +1776,8 @@
 	case NFA_BOL:		STRCPY(code, "NFA_BOL "); break;
 	case NFA_EOW:		STRCPY(code, "NFA_EOW "); break;
 	case NFA_BOW:		STRCPY(code, "NFA_BOW "); break;
+	case NFA_EOF:		STRCPY(code, "NFA_EOF "); break;
+	case NFA_BOF:		STRCPY(code, "NFA_BOF "); break;
 	case NFA_STAR:		STRCPY(code, "NFA_STAR "); break;
 	case NFA_PLUS:		STRCPY(code, "NFA_PLUS "); break;
 	case NFA_NOT:		STRCPY(code, "NFA_NOT "); break;
@@ -3705,6 +3703,17 @@
 		break;
 	    }
 
+	    case NFA_BOF:
+		if (reglnum == 0 && reginput == regline
+					&& (!REG_MULTI || reg_firstlnum == 1))
+		    addstate_here(thislist, t->state->out, &t->sub, &listidx);
+		break;
+
+	    case NFA_EOF:
+		if (reglnum == reg_maxline && curc == NUL)
+		    addstate_here(thislist, t->state->out, &t->sub, &listidx);
+		break;
+
 #ifdef FEAT_MBYTE
 	    case NFA_COMPOSING:
 	    {