pattern-matchingdfa

What strings are accepted by the pattern "^[ab]?|c?$"?

What I have gathered till now:

  1. ^ -> match the first symbol
  2. $ -> match the last symbol
  3. [] -> set of characters that can be in the position
  4. | -> the "OR" operator
  5. ? -> the previous condition is optional

What I think the pattern means:
The line has to either begin with an a or a b or has to end with a c or has to be an empty string. I am having trouble drawing the dfa for the pattern though. What's throwing me off is the "optional" symbol. I am not able to understand what strings won't be accepted in the language.

Can someone point me in the right direction?

Solution

  • ^ matches the start of the line.

    [ab]? matches "a", or "b", or nothing.

    c? matches "c", or nothing.

    $ matches the end of the line.

    So, I think these lines will match:

    (empty line)
a
b
c