Snippets Groups Projects

"...automata-library.git" did not exist on "0fb7a6847691f05f5574b5cb4bc10ed27a402fa3"

algo: Fix AutomataConcatenation when first automaton has a word of len 1

Tomáš Pecka authored 3 years ago

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.

0fb7a684

0fb7a684 3 years ago

Name	Last commit	Last update
CMake
agui2
alib2abstraction
alib2algo
alib2algo_experimental
alib2aux
alib2cli
alib2common
alib2data
alib2data_experimental
alib2dummy
alib2elgo
alib2graph_algo
alib2graph_data
alib2gui
alib2measure
alib2raw
alib2raw_cli_integration
alib2std
alib2str
alib2str_cli_integration
alib2xml
aql2
docs
examples2
extra
lib/catch2
tests
.clang-tidy
.clang-tidy-ignore
.editorconfig
.gitignore
.gitlab-ci.yml
CMakeLists.txt
DEVELOPER_NOTES
LICENSE
README.md
build.sh

Algorithms Library Toolkit

For documentation and quickstart see our website.

What is it?

The Algorithms library toolkit (ALT) is a collection of implementations of various types of automata, grammars, and other common structires along with mathematical implementation of algorithms over these structures. Originaly developed at Faculty of Information Technology of Czech Technical University in Prague. It supposed to be a reference implementation of formal algorithms as-are in papers. It's interface allows practical reuse of existing algorithms in form of by pipe comunicating, partially using a query language in command line, and partially using a GUI interface.

The Latest Version

Packages and docker images with latest stable and nightly versions can be found visiting at website.

Requirements

C++-20 capable compiler, cmake (plus make or ninja). Linux platform (99.9 % percent of the features should work on different platforms but there are still small parts of code that are Linux only).

Build tools:

cmake >= 3.12
g++ >= 10.0 or clang++ >= 9.0 (compilation in C++20)

Libraries:

tclap (header-only argument parsing library, fetched by CMake and git automatically during build process)
libxml2
readline

For GUI, you will need also the following libraries. However, GUI does not build by default now. Use cmake option -DWITH_AGUI=ON to build it:

Qt5-qtbase >= 5.7
jsoncpp
graphviz

Optional dependencies:

doxygen (for documentation generation)
graphviz (for documentation generation and automata visualizations)

Installation

You can build from sources using cmake or download packages or sources of stable release We recommend running the testsuite using ctest as well.

We support common cmake options, additional ones are:

-DWITH_AGUI=ON to build deprecated GUI part
-DWITH_DOCS=ON to build a doxygen target to generate API docs.

Documentation

In order to generate API documentation, run cmake with -DWITH_DOCS=ON and then invoke doxygen target. The high-level documentation is located at ALT website.

Contributing

Feel free to fork this project and send your merge requests there. In case you want to run our Gitlab CI, remove all the following parts of code in .gitlab-ci.yml.

tags:
 - altbuilder

Developers

Editor configuration for this project is provided by editorconfig.

Issues and bugs

Please use our issue tracker.

Licensing

Please see LICENSE file.

Contacts

You can contact the authors using our issue tracker or by email.

Authors

Ing. Jan Trávníček,
Ing. Tomáš Pecka,
Ing. Štěpán Plachý,
et. al.