Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Concepts
ToPostfixPushdownAutomaton.h
Go to the documentation of this file.
1
6/*
7 * This file is part of Algorithms library toolkit.
8 * Copyright (C) 2017 Jan Travnicek (jan.travnicek@fit.cvut.cz)
9
10 * Algorithms library toolkit is free software: you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License as published by
12 * the Free Software Foundation, either version 3 of the License, or
13 * (at your option) any later version.
14
15 * Algorithms library toolkit is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
19
20 * You should have received a copy of the GNU General Public License
21 * along with Algorithms library toolkit. If not, see <http://www.gnu.org/licenses/>.
22 */
23
24#pragma once
25
26#include <automaton/TA/DFTA.h>
27#include <automaton/TA/NFTA.h>
28#include <automaton/PDA/NPDA.h>
29#include <automaton/PDA/DPDA.h>
30
32#include <alphabet/EndSymbol.h>
33
34namespace automaton {
35
36namespace convert {
37
42public:
48 template < class SymbolType, class StateType >
50
56 template < class SymbolType, class StateType >
58};
59
60template < class SymbolType, class StateType >
63
64 for ( const auto & rankedSymbol : dfta.getInputAlphabet ( ) ) {
65 automaton.addInputSymbol ( rankedSymbol );
66 }
67 automaton.addInputSymbol ( alphabet::EndSymbol ( ) );
68
69 for ( const StateType & state : dfta.getStates ( ) ) {
70 automaton.addPushdownStoreSymbol ( state );
71 }
72
73 for (const auto & transition : dfta.getTransitions()) {
74 ext::vector < ext::variant < StateType, alphabet::BottomOfTheStackSymbol > > pop ( transition.first.second.rbegin ( ), transition.first.second.rend ( ) );
76 automaton.addTransition ( automaton.getInitialState ( ), transition.first.first, pop, automaton.getInitialState ( ), push );
77 }
78
79 auto finalPDAState = 'r';
80 automaton.addState ( finalPDAState );
81 automaton.addFinalState ( finalPDAState );
82
83 for ( const auto & finalState : dfta.getFinalStates ( ) ) {
86 automaton.addTransition ( automaton.getInitialState ( ), alphabet::EndSymbol ( ), pop, finalPDAState, push );
87 }
88
89 return automaton;
90}
91
92template < class SymbolType, class StateType >
95
96 for ( const auto & symbol : nfta.getInputAlphabet ( ) ) {
97 automaton.addInputSymbol ( symbol );
98 }
99 automaton.addInputSymbol ( alphabet::EndSymbol ( ) );
100
101 for ( const StateType & state : nfta.getStates ( ) ) {
102 automaton.addPushdownStoreSymbol ( state );
103 }
104
105 for ( const auto & transition : nfta.getTransitions ( ) ) {
106 ext::vector < ext::variant < StateType, alphabet::BottomOfTheStackSymbol > > pop ( transition.first.second.rbegin ( ), transition.first.second.rend ( ) );
108 automaton.addTransition (automaton.getInitialState ( ), transition.first.first, pop, automaton.getInitialState ( ), push );
109 }
110
111 char finalPDAState = 'r';
112 automaton.addState ( finalPDAState );
113 automaton.addFinalState ( finalPDAState );
114
115 for ( const StateType & finalState : nfta.getFinalStates ( ) ) {
118 automaton.addTransition ( automaton.getInitialState ( ), alphabet::EndSymbol ( ), pop, finalPDAState, push );
119 }
120
121 return automaton;
122}
123
124} /* namespace convert */
125
126} /* namespace automaton */
127
Represents bottom of the stack symbol used in the visibly pushdown automata.
Definition: BottomOfTheStackSymbol.h:35
Represents end symbol used as termation symbol of a string.
Definition: EndSymbol.h:35
Nondeterministic finite tree automaton without epsilon transitions. Accepts regular tree languages.
Definition: DFTA.h:74
const ext::map< ext::pair< common::ranked_symbol< SymbolType >, ext::vector< StateType > >, StateType > & getTransitions() const &
Definition: DFTA.h:289
const ext::set< common::ranked_symbol< SymbolType > > & getInputAlphabet() const &
Definition: DFTA.h:203
const ext::set< StateType > & getFinalStates() const &
Definition: DFTA.h:154
const ext::set< StateType > & getStates() const &
Definition: DFTA.h:105
Deterministic pushdown automaton. Accepts subset of context free languages.
Definition: DPDA.h:78
Nondeterministic finite tree automaton without epsilon transitions. Accepts regular tree languages.
Definition: NFTA.h:72
const ext::set< StateType > & getFinalStates() const &
Definition: NFTA.h:159
const ext::multimap< ext::pair< common::ranked_symbol< SymbolType >, ext::vector< StateType > >, StateType > & getTransitions() const &
Definition: NFTA.h:294
const ext::set< StateType > & getStates() const &
Definition: NFTA.h:110
const ext::set< common::ranked_symbol< SymbolType > > & getInputAlphabet() const &
Definition: NFTA.h:208
Definition: NPDA.h:74
Definition: ToPostfixPushdownAutomaton.h:41
static automaton::DPDA< ext::variant< common::ranked_symbol< SymbolType >, alphabet::EndSymbol >, ext::variant< StateType, alphabet::BottomOfTheStackSymbol >, char > convert(const automaton::DFTA< SymbolType, StateType > &dfta)
Definition: ToPostfixPushdownAutomaton.h:61
Implementation of the variant class allowing to store any type of those listed in the template parame...
Definition: variant.hpp:98
Class extending the vector class from the standard library. Original reason is to allow printing of t...
Definition: vector.hpp:45
typename T::StateType StateType
Definition: ToGrammarLeftRG.h:64
Definition: ToGrammar.h:31
Definition: converterCommon.hpp:8