Regex for string using GNU C regex library

The pattern in your question was consuming the first letter in state with [^#], which left the match unable to proceed because it tries to match tate against the pattern \(state\).

You passed the flag REG_EXTENDED which means you don't escape capturing parentheses but do escape literal parentheses.

With regular expressions, say what you do want to match:

^[ \\t]*(state)[ \\t]*:.*$

as in

#include <stdio.h>
#include <regex.h>

int main(int argc, char **argv)
{
  struct {
    const char *input;
    int expect;
  } tests[] = {
    /* should match */
    { "state : q0", 1 },
    { "state: q0",  1 },
    { "state:q0s",  1 },

    /* should not match */
    { "#state :q0",  0 },
    { "state q0",    0 },
    { "# state :q0", 0 },
  };
  int i;
  regex_t start_state;
  const char *pattern = "^[ \\t]*(state)[ \\t]*:.*$";

  if (regcomp(&start_state, pattern, REG_EXTENDED)) {
    fprintf(stderr, "%s: bad pattern: '%s'\n", argv[0], pattern);
    return 1;
  }

  for (i = 0; i < sizeof(tests)/sizeof(tests[0]); i++) {
    int status = regexec(&start_state, tests[i].input, 0, NULL, 0);

    printf("%s: %s (%s)\n", tests[i].input,
                            status == 0 ? "match" : "no match",
                            !status == !!tests[i].expect
                              ? "PASS" : "FAIL");
  }

  regfree(&start_state);

  return 0;
}

Output:

state : q0: match (PASS)
state: q0: match (PASS)
state:q0s: match (PASS)
#state :q0: no match (PASS)
state q0: no match (PASS)
# state :q0: no match (PASS)