AutomataConcatenationTest.cpp

#include <alib/list>
#include "AutomataConcatenationTest.h"

#include "automaton/transform/AutomataConcatenation.h"
#include "automaton/transform/AutomataConcatenationEpsilonTransition.h"

#include "automaton/simplify/MinimizeBrzozowski.h"
#include "automaton/simplify/Normalize.h"
#include "automaton/simplify/EpsilonRemoverIncoming.h"
#include "automaton/simplify/Trim.h"
#include "automaton/simplify/Total.h"
#include "automaton/determinize/Determinize.h"

CPPUNIT_TEST_SUITE_NAMED_REGISTRATION( AutomataConcatenationTest, "automaton" );
CPPUNIT_TEST_SUITE_REGISTRATION( AutomataConcatenationTest );

void AutomataConcatenationTest::setUp() {
}

void AutomataConcatenationTest::tearDown() {
}

void AutomataConcatenationTest::testAutomataConcatenation() {
	// based on Melichar, 2.79

	DefaultStateType q1a = DefaultStateType("1");
	DefaultStateType q2a = DefaultStateType("2");
	DefaultStateType q0a = DefaultStateType("0");
	DefaultStateType q1b = DefaultStateType("1'");
	DefaultStateType q2b = DefaultStateType("2'");
	DefaultStateType q0b = DefaultStateType("0'");
	DefaultStateType q0102 = DefaultStateType("q0102");
	DefaultSymbolType a(DefaultSymbolType('a')), b(DefaultSymbolType('b'));

	automaton::DFA<> m1(q1a);
	automaton::DFA<> m2(q1b);
	automaton::NFA < >  m3(q1a);

	m1.setInputAlphabet({a, b});
	m1.setStates({q1a, q2a, q0a});
	m1.addTransition(q1a, a, q2a);
	m1.addTransition(q1a, b, q0a);
	m1.addTransition(q2a, a, q2a);
	m1.addTransition(q2a, b, q0a);
	m1.addTransition(q0a, a, q0a);
	m1.addTransition(q0a, b, q0a);
	m1.addFinalState(q2a);

	m2.setInputAlphabet({a, b});
	m2.setStates({q1b, q2b});
	m2.addTransition(q1b, b, q2b);
	m2.addTransition(q2b, b, q2b);
	m2.addFinalState(q2b);

	m3.setInputAlphabet({a, b});
	m3.setStates({q1a, q1b, q2a, q2b, q0a, q0b, q0102});
	m3.addTransition(q1a, a, q2a);
	m3.addTransition(q1a, a, q1b);
	m3.addTransition(q1a, b, q0a);
	m3.addTransition(q2a, a, q2a);
	m3.addTransition(q2a, a, q1b);
	m3.addTransition(q2a, b, q0a);
	m3.addTransition(q0a, a, q0a);
	m3.addTransition(q0a, b, q0a);
	m3.addTransition(q1b, a, q0b);
	m3.addTransition(q1b, b, q2b);
	m3.addTransition(q2b, a, q0b);
	m3.addTransition(q2b, b, q2b);
	m3.addTransition(q0b, a, q0b);
	m3.addTransition(q0b, b, q0b);
	m3.setFinalStates({q2b});

	auto u11 = automaton::transform::AutomataConcatenationEpsilonTransition::concatenation(automaton::NFA<>(automaton::DFA<>(m1)), automaton::NFA < > (m2));
	auto u12 = automaton::transform::AutomataConcatenationEpsilonTransition::concatenation(automaton::DFA<>(m1), automaton::DFA<>(m2));
	auto u21 = automaton::transform::AutomataConcatenation::concatenation(automaton::NFA<>(automaton::DFA<>(m1)), automaton::NFA < > (m2));
	auto u22 = automaton::transform::AutomataConcatenation::concatenation(automaton::DFA<>(m1), automaton::DFA<>(m2));

	automaton::DFA < DefaultSymbolType, unsigned > umdfa (automaton::simplify::Normalize::normalize(automaton::simplify::Trim::trim(automaton::simplify::MinimizeBrzozowski::minimize(automaton::simplify::EpsilonRemoverIncoming::remove(m3)))));
	automaton::DFA < DefaultSymbolType, unsigned > umdfa11(automaton::simplify::Normalize::normalize(automaton::simplify::Trim::trim(automaton::simplify::MinimizeBrzozowski::minimize(automaton::simplify::EpsilonRemoverIncoming::remove(u11)))));
	automaton::DFA < DefaultSymbolType, unsigned > umdfa12(automaton::simplify::Normalize::normalize(automaton::simplify::Trim::trim(automaton::simplify::MinimizeBrzozowski::minimize(automaton::simplify::EpsilonRemoverIncoming::remove(u12)))));
	automaton::DFA < DefaultSymbolType, unsigned > umdfa21(automaton::simplify::Normalize::normalize(automaton::simplify::Trim::trim(automaton::simplify::MinimizeBrzozowski::minimize(automaton::simplify::EpsilonRemoverIncoming::remove(u21)))));
	automaton::DFA < DefaultSymbolType, unsigned > umdfa22(automaton::simplify::Normalize::normalize(automaton::simplify::Trim::trim(automaton::simplify::MinimizeBrzozowski::minimize(automaton::simplify::EpsilonRemoverIncoming::remove(u22)))));

	CPPUNIT_ASSERT(umdfa11 == umdfa);
	CPPUNIT_ASSERT(umdfa12 == umdfa);
	CPPUNIT_ASSERT(umdfa21 == umdfa);
	CPPUNIT_ASSERT(umdfa22 == umdfa);

}