trimTest.cpp

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

#include "automaton/simplify/Trim.h"
#include "grammar/simplify/Trim.h"

#include "automaton/FSM/DFA.h"
#include "grammar/Regular/RightRG.h"
#include "automaton/TA/DFTA.h"

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

void trimTest::setUp() {
}

void trimTest::tearDown() {
}

void trimTest::testTrimAutomaton() {
	automaton::DFA < > automaton(DefaultStateType(1));

	automaton.addState(DefaultStateType(1));
	automaton.addState(DefaultStateType(2));
	automaton.addState(DefaultStateType(3));
	automaton.addInputSymbol(DefaultSymbolType("a"));
	automaton.addInputSymbol(DefaultSymbolType("b"));

	automaton.addTransition(DefaultStateType(1), DefaultSymbolType("a"), DefaultStateType(2));
	automaton.addTransition(DefaultStateType(2), DefaultSymbolType("b"), DefaultStateType(1));
	automaton.addTransition(DefaultStateType(3), DefaultSymbolType("b"), DefaultStateType(1));

	automaton.addFinalState(DefaultStateType(1));

	automaton::DFA<> trimed = automaton::simplify::Trim::trim(automaton);

	CPPUNIT_ASSERT(trimed.getStates().size() == 2);
}

void trimTest::testTrimGrammar() {
	grammar::RightRG < > rrGrammar(DefaultSymbolType(1));

	rrGrammar.addNonterminalSymbol(DefaultSymbolType(1));
	rrGrammar.addNonterminalSymbol(DefaultSymbolType(2));
	rrGrammar.addNonterminalSymbol(DefaultSymbolType(3));
	rrGrammar.addNonterminalSymbol(DefaultSymbolType(4));
	rrGrammar.addNonterminalSymbol(DefaultSymbolType(5));
	rrGrammar.addNonterminalSymbol(DefaultSymbolType(6));
	rrGrammar.addTerminalSymbol(DefaultSymbolType("a"));
	rrGrammar.addTerminalSymbol(DefaultSymbolType("b"));
	
	rrGrammar.addRule(DefaultSymbolType(1), ext::make_pair(DefaultSymbolType("a"), DefaultSymbolType(2)));
	rrGrammar.addRule(DefaultSymbolType(2), ext::make_pair(DefaultSymbolType("b"), DefaultSymbolType(3)));
	rrGrammar.addRule(DefaultSymbolType(3), DefaultSymbolType("a"));

	rrGrammar.addRule(DefaultSymbolType(4), ext::make_pair(DefaultSymbolType("b"), DefaultSymbolType(5)));
	rrGrammar.addRule(DefaultSymbolType(5), DefaultSymbolType("a"));
	rrGrammar.addRule(DefaultSymbolType(5), ext::make_pair(DefaultSymbolType("b"), DefaultSymbolType(2)));
	rrGrammar.addRule(DefaultSymbolType(6), ext::make_pair(DefaultSymbolType("b"), DefaultSymbolType(6)));

	grammar::RightRG < > trimed = grammar::simplify::Trim::trim(rrGrammar);

	CPPUNIT_ASSERT(trimed.getNonterminalAlphabet().size() == 3);
}

void trimTest::testTrimDFTA() {
	automaton::DFTA < > automaton;

	ext::vector<DefaultStateType> q;
	for (int i = 0; i <= 11; ++i) {
		DefaultStateType state (i);
		q.push_back(state);
		automaton.addState(state);
	}
	automaton.addFinalState(q[2]);
	automaton.addFinalState(q[11]);

	const common::ranked_symbol < > a ("a", 2);
	const common::ranked_symbol < > b ("b", 1);
	const common::ranked_symbol < > c ("c", 0);
	automaton.addInputSymbol(a);
	automaton.addInputSymbol(b);
	automaton.addInputSymbol(c);

	automaton.addTransition(c, {}, q[0]);
	automaton.addTransition(a, {q[0], q[0]}, q[1]);
	automaton.addTransition(b, {q[1]}, q[2]);

	//unreachable and useless
	automaton.addTransition(a, {q[3], q[4]}, q[5]);
	automaton.addTransition(b, {q[5]}, q[6]);

	//useless
	automaton.addTransition(a, {q[2], q[2]}, q[7]);
	automaton.addTransition(a, {q[7], q[7]}, q[8]);

	//unreachable
	automaton.addTransition(a, {q[9], q[9]}, q[10]);
	automaton.addTransition(a, {q[10], q[10]}, q[11]);

	automaton::DFTA<> trimed = automaton::simplify::Trim::trim(automaton);

	automaton::DFTA<> correct;
	correct.addState(q[0]);
	correct.addState(q[1]);
	correct.addState(q[2]);
	correct.addFinalState(q[2]);
	correct.addInputSymbol(a);
	correct.addInputSymbol(b);
	correct.addInputSymbol(c);
	correct.addTransition(c, {}, q[0]);
	correct.addTransition(a, {q[0], q[0]}, q[1]);
	correct.addTransition(b, {q[1]}, q[2]);

	CPPUNIT_ASSERT(trimed == correct);
}