This new easy algorithm checks whether a regexp's language is an
infinite language.
Also adding an AQL test to compare with the same algorithm on finite
automata.

Introduce a new algorithm, regexp::properties::LanguageIsEpsilon to
check whether a language of a regexp is exactly equal to a language of
epsilon regexp.
This will be later useful in checking whether the language of a regexp
is infinite.

Similarly to previous commit, let's make this clear. We are soon going
to add a new algorithm that will check if the language is equal to
epsilon, so let's differentiate.

The name regexp::properties::RegExpEmpty is not that expressive. Let's
make clear what is going on.

The algorithm, taken from BI-AAG course @ FIT CTU did not work
correctly when first automaton accepts a word of length 1.

There are two bugs. First, the set of final states was wrong. This was
the easy part to spot.
Second, we sometimes miss some transitions.

Consider these two automata:
 DFA a b
 ><A B -
  <B - -

 DFA a b
 ><C - -

The algorithm would result in this:
 DFA a   b
 ><S B   C
   A B|C -
   B -   -
  <C -   C

Which is of course wrong because the first automaton accepts "a + #E"
and the second one accepts a language of "b*". However, the result
doesn't accept words from neither "a" nor "ab*" which is in language
"(a+#E)b*".

The problem is that for every transition in the first automaton that
leads to a final state we create a new transition to an initial state of
the second automaton. This effectively says that "ok, we are done with
first automaton, we would accept. Let's continue from the initial state
of the second automaton".
Also, when we create a new initial state, we *only* copy transitions from
both initial states there. But if the word is of length 1 and is to be
accepted by the first automaton, we are missing this "transition to second
automaton".
In our example above, we need to add a transition (S, a) -> C and it's
fine.

Jan Trávníček authored 3 years ago and Jan Trávníček committed 3 years ago

breaking change!

... because most developers were copy-pasting the preambule anyway and
did not pay any attention to change it.

Also, I think that git does better job in managing that.

The case (b*+a)* was only optimized to (b+a)* by lemma V4.

Algorithm automaton::transform::AutomatonIteration resulted in wrong
output when the input automaton had a transition from the initial state to a
final state.
If such transitions exists, we must also add a transition from the new
initial state to the old initial state in the new automata.

Added a test case for this particular case.

Closes #211

The tests for iteration were "messy". It was not clear what are they
doing and also we tested two algorithms in one test case.

Split those algorithms and make them clear -- test only for expected
output.

Also make the test section names more clear

I redesigned the algorithm to make it similar to NPDA run implementation, most
importantly to handle cycles, also not even the very basic test that I
introduced didn't pass.

Additionaly, the graphStructuredStacks used to track the pushdown store and output were
incorrectly parametrized with InputSymbolType instead of PushdownStoreSymbolType
and OutputSymbolType.

NPDA execution through BFS-like simulation. Only exposed via Accept algo.

The algorithm generated rules of the automaton with the top of the pushdown
store symbol on the right, which is according to the algorithm, however, the
representation of PDAs and every PDA processing algorithm assumes the top of the
pushdown store is on the left.