Here is a RE Z*Z+ and here is a string it matches:
ZZZZ .
What part of the string does Z* match?
ZZZ — it must leave the last "Z" so the Z+ has something to match.
Is there a simpler RE that matches the same set of strings?
Z+
Here is a RE A+A+ and here is the automaton
that matches it
The automaton is non-deterministic. If (for example) the automaton is in state q1 and the current character is 'A' it has a choice of transitions. "Greedy" behavior is that the automaton will stay in q1 unless doing so will prevent it from reaching the final state.
A non-deterministic automaton matches a string if there is a possible path through it that consumes each of the characters in the string. Not all paths have to match the string.
Here is a regular expression: [ABC]*[CD]
Does the expression match these strings?
| String | ABC | CBCC | CDC | DD | CCAAC | CCCC | AA | CAB |
|---|---|---|---|---|---|---|---|---|
| Match or Reject? |