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
ToGrammarLeftRG.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
25#pragma once
26
28#include <automaton/FSM/NFA.h>
29#include <automaton/FSM/DFA.h>
30
31#include <alib/map>
33
35
36namespace automaton {
37
38namespace convert {
39
44public:
54 template < class T >
55 requires isDFA < T > || isNFA < T >
57
58};
59
60template < class T >
61requires isDFA < T > || isNFA < T >
63 using SymbolType = typename T::SymbolType;
64 using StateType = typename T::StateType;
65
66 // step 2
67 grammar::LeftRG < SymbolType, StateType > grammar(alphabet::InitialSymbol::instance < StateType > ( ) );
68
69 // step 1
70 grammar.setTerminalAlphabet ( automaton.getInputAlphabet ( ) );
71
72 for ( const auto & state : automaton.getStates ( ) ) {
73 grammar.addNonterminalSymbol ( state );
74 }
75
76 // step 3 - create set of P in G
77 for ( const auto & transition : automaton.getTransitions ( ) ) {
78 const StateType & from = transition.first.first;
79 const SymbolType & input = transition.first.second;
80 const StateType & to = transition.second;
81
82 // 3a
83 grammar.addRule ( to, ext::make_pair ( from, input ) );
84
85 if ( automaton.getFinalStates ( ).contains ( to ) )
86 grammar.addRule ( grammar.getInitialSymbol ( ), ext::make_pair ( from, input ) );
87
88 if ( automaton.getInitialState ( ) == from ) {
89 grammar.addRule ( to, input );
90
91 if ( automaton.getFinalStates ( ).contains ( to ) )
92 grammar.addRule ( grammar.getInitialSymbol ( ), input );
93 }
94 }
95
96 if ( automaton.getFinalStates ( ).contains ( automaton.getInitialState ( ) ) )
97 grammar.setGeneratesEpsilon ( true );
98
99 return grammar;
100}
101
102} /* namespace convert */
103
104} /* namespace automaton */
105
Definition: ToGrammarLeftRG.h:43
static grammar::LeftRG< typename T::SymbolType, typename T::StateType > convert(const T &automaton)
Left regular grammar in Chomsky hierarchy or type 3 in Chomsky hierarchy. Generates regular languages...
Definition: LeftRG.h:70
typename T::StateType StateType
Definition: ToGrammarLeftRG.h:64
return grammar
Definition: ToGrammarLeftRG.h:99
typename T::SymbolType SymbolType
Definition: ReachableStates.h:176
Definition: ToGrammar.h:31
Definition: converterCommon.hpp:8
constexpr auto make_pair(T1 &&x, T2 &&y)
Definition: pair.hpp:79
Definition: ToAutomaton.h:24