Combining ^ with | in regex leads to unexpected behavior

[koniksedy]

When constructing an NFA from a regular expression that combines ^ and |, the resulting automaton can have unexpected languages (only partial or even empty).

Example

Consider the expression ^a|b. I interpret this as (^a)|(b), expecting both a and b to be included in the language. However, the following NFAs (without trimming or renamed states) produce different results:

1. Regex ^a|b: This results in an automaton with an empty language.

   @NFA-explicit
   %Alphabet-auto
   %Initial q3
   %Final q6
   q4 301 q6
   q5 97 q6
   

2. Regex (^a)|b: This results in an automaton with the language {b}, although I would expect it to include a as well.

   @NFA-explicit
   %Alphabet-auto
   %Initial q3
   %Final q8 q7
   q3 98 q8
   q4 98 q8
   q6 301 q7
   

3. Regex a|b: This produces an automaton with the expected language {a, b}.

   @NFA-explicit
   %Alphabet-auto
   %Initial q3
   %Final q4
   q3 97 q4
   q3 98 q4
   

Omitting ^ in regexes could partially suppress this issue.

[Adda0]

This issue is now fixed through #459. The more complicated cases from other issues (#457, #437) will have to be tested after merging #461.