formalang/tests/invertFDFA/InvertFDFA.cpp

#include <gtest/gtest.h>
#include <random>
#include "regular/RegularTree.hpp"
#include "converters/RegularToNFA.hpp"
#include "converters/NFAToDFA.hpp"
#include "converters/DFAToMinDFA.hpp"
#include "converters/DFAToFDFA.hpp"
#include "converters/InvertFDFA.hpp"

using namespace regular;
using namespace NFA;
using namespace DFA;
using namespace converters;

extern std::mt19937 rnd;

extern std::string GenerateRandomString(std::vector<char> alphabet, size_t len);

TEST(invert_DFA, a_star) {
  RegularTree r("a*");
  NFAGraph NFA_tree = RegularToNFAGraph(std::move(r));
  DFAGraph DFA_graph = NFAGraphToDFAGraph(std::move(NFA_tree));
  DFA_graph = DFAGraphToMinDFAGraph(std::move(DFA_graph));

  DFA_graph = DFAGraphToFDFAGraph(std::move(DFA_graph), {'a', 'b', 'c', 'd'});
  DFA_graph = InvertFDFAGraph(std::move(DFA_graph));
  DFA_graph = DFAGraphToMinDFAGraph(std::move(DFA_graph));

  std::string s = "";
  for (int i = 0; i < 100; ++i) {
    ASSERT_EQ(DFA_graph.Accepted(s), false);
    s += "a";
  }
}

TEST(invert_DFA, a_plus) {
  std::string regulars[] = {"a+", "(a)+", "(a+)"};
  for (const auto& regular: regulars) {
    RegularTree r(regular);
    NFAGraph NFA_tree = RegularToNFAGraph(std::move(r));
    DFAGraph DFA_graph = NFAGraphToDFAGraph(std::move(NFA_tree));
    DFA_graph = DFAGraphToMinDFAGraph(std::move(DFA_graph));

    DFA_graph = DFAGraphToFDFAGraph(std::move(DFA_graph), {'a', 'b', 'c', 'd'});
    DFA_graph = InvertFDFAGraph(std::move(DFA_graph));
    DFA_graph = DFAGraphToMinDFAGraph(std::move(DFA_graph));

    std::string s = "";
    ASSERT_EQ(DFA_graph.Accepted(s), true);
    s += "a";
    for (int i = 0; i < 100; ++i) {
      ASSERT_EQ(DFA_graph.Accepted(s), false);
      s += "a";
    }
  }
}

TEST(invert_DFA, abc) {
  std::string regulars[] = {"abc"};
  for (const auto& regular: regulars) {
    RegularTree r(regular);
    NFAGraph NFA_tree = RegularToNFAGraph(std::move(r));
    DFAGraph DFA_graph = NFAGraphToDFAGraph(std::move(NFA_tree));
    DFA_graph = DFAGraphToMinDFAGraph(std::move(DFA_graph));

    DFA_graph = DFAGraphToFDFAGraph(std::move(DFA_graph), {'a', 'b', 'c', 'd'});
    DFA_graph = InvertFDFAGraph(std::move(DFA_graph));
    DFA_graph = DFAGraphToMinDFAGraph(std::move(DFA_graph));

    ASSERT_EQ(DFA_graph.Accepted("abc"), false);
    for (int i = 0; i < 1000; ++i) {
      auto s = GenerateRandomString({'a', 'b', 'c', 'd'}, rnd() % 10);
      if (s == "abc") continue;
      ASSERT_EQ(DFA_graph.Accepted(s), true);
    }
  }
}

TEST(invert_DFA, a_or_b_or_c) {
  std::string regulars[] = {};
  for (const auto& regular: regulars) {
    RegularTree r("a|b|c");
    NFAGraph NFA_tree = RegularToNFAGraph(std::move(r));
    DFAGraph DFA_graph = NFAGraphToDFAGraph(std::move(NFA_tree));
    DFA_graph = DFAGraphToMinDFAGraph(std::move(DFA_graph));

    DFA_graph = DFAGraphToFDFAGraph(std::move(DFA_graph), {'a', 'b', 'c', 'd'});
    DFA_graph = InvertFDFAGraph(std::move(DFA_graph));
    DFA_graph = DFAGraphToMinDFAGraph(std::move(DFA_graph));

    ASSERT_EQ(DFA_graph.Accepted("a"), false);
    ASSERT_EQ(DFA_graph.Accepted("b"), false);
    ASSERT_EQ(DFA_graph.Accepted("c"), false);
    for (int i = 0; i < 1000; ++i) {
      auto s = GenerateRandomString({'a', 'b', 'c', 'd'}, rnd() % 10);
      if (s == "a") continue;
      if (s == "b") continue;
      if (s == "c") continue;
      ASSERT_EQ(DFA_graph.Accepted(s), true);
    }
  }
}

TEST(invert_DFA, a_star_or_b_star_or_c_star) {
  std::string regulars[] = {"a*|b*|c*", "(a*)|(b*|c*)", "(a*|b*|c*)", "((a*)|(b*)|(c*))"};
  for (const auto& regular: regulars) {
    RegularTree r(regular);
    NFAGraph NFA_tree = RegularToNFAGraph(std::move(r));
    DFAGraph DFA_graph = NFAGraphToDFAGraph(std::move(NFA_tree));
    DFA_graph = DFAGraphToMinDFAGraph(std::move(DFA_graph));

    DFA_graph = DFAGraphToFDFAGraph(std::move(DFA_graph), {'a', 'b', 'c', 'd'});
    DFA_graph = InvertFDFAGraph(std::move(DFA_graph));
    DFA_graph = DFAGraphToMinDFAGraph(std::move(DFA_graph));

    auto check = [](const std::string str) {
      std::set<char> s(str.begin(), str.end());
      if (s.size() == 0)
        return true;
      else {
        if (s.size() == 1)
          return *s.begin() != 'd';
        else
          return false;
      }
    };

    ASSERT_EQ(DFA_graph.Accepted(""), false);
    for (int i = 0; i < 1000; ++i) {
      auto s = GenerateRandomString({'a', 'b', 'c', 'd'}, rnd() % 10);

      ASSERT_EQ(DFA_graph.Accepted(s), !check(s));
    }
  }
}

TEST(invert_DFA, _a_star_or_b_star_or_c_star_plus) {
  RegularTree r("(a*|b*|c*)+");
  NFAGraph NFA_tree = RegularToNFAGraph(std::move(r));
  DFAGraph DFA_graph = NFAGraphToDFAGraph(std::move(NFA_tree));
  DFA_graph = DFAGraphToMinDFAGraph(std::move(DFA_graph));

  DFA_graph = DFAGraphToFDFAGraph(std::move(DFA_graph), {'a', 'b', 'c', 'd'});
  DFA_graph = InvertFDFAGraph(std::move(DFA_graph));
  DFA_graph = DFAGraphToMinDFAGraph(std::move(DFA_graph));

  auto check = [](const std::string str) {
    std::set<char> s(str.begin(), str.end());
    return s.find('d') == s.end();
  };

  ASSERT_EQ(DFA_graph.Accepted(""), false);
  for (int i = 0; i < 1000; ++i) {
    auto s = GenerateRandomString({'a', 'b', 'c', 'd'}, rnd() % 10);

    ASSERT_EQ(DFA_graph.Accepted(s), !check(s));
  }
}

TEST(invert_DFA, _a_or_b_or_c_star_plus) {
  RegularTree r("(a|b|c*)+");
  NFAGraph NFA_tree = RegularToNFAGraph(std::move(r));
  DFAGraph DFA_graph = NFAGraphToDFAGraph(std::move(NFA_tree));
  DFA_graph = DFAGraphToMinDFAGraph(std::move(DFA_graph));

  DFA_graph = DFAGraphToFDFAGraph(std::move(DFA_graph), {'a', 'b', 'c', 'd'});
  DFA_graph = InvertFDFAGraph(std::move(DFA_graph));
  DFA_graph = DFAGraphToMinDFAGraph(std::move(DFA_graph));

  auto check = [](const std::string str) {
    std::set<char> s(str.begin(), str.end());
    return s.find('d') == s.end();
  };

  ASSERT_EQ(DFA_graph.Accepted(""), false);
  for (int i = 0; i < 1000; ++i) {
    auto s = GenerateRandomString({'a', 'b', 'c', 'd'}, rnd() % 10);

    ASSERT_EQ(DFA_graph.Accepted(s), !check(s));
  }
}