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

32 views Asked by At

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?

1

There are 1 answers

6
John Gordon On BEST ANSWER

^ 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