Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
|
Deterministic pushdown automaton requiring a symbol pop from pushdown store on each transition use. Accepts subset of context free languages. More...
#include <SinglePopDPDA.h>
Public Types | |
typedef InputSymbolTypeT | InputSymbolType |
typedef PushdownStoreSymbolTypeT | PushdownStoreSymbolType |
typedef StateTypeT | StateType |
Friends | |
ext::ostream & | operator<< (ext::ostream &out, const SinglePopDPDA &instance) |
Deterministic pushdown automaton requiring a symbol pop from pushdown store on each transition use. Accepts subset of context free languages.
Definition A = (Q, T, G, I, Z, \delta, F), Q (States) = nonempty finite set of states, T (TerminalAlphabet) = finite set of terminal symbols - having this empty won't let automaton do much though, G (PushdownStoreAlphabet) = finite set of pushdown store symbol - having this empty makes the automaton equivalent to DFA I (InitialState) = initial state, Z (InitialPushdownStoreSymbol) = initial pushdown store symbol \delta = transition function of the form A \times a \times g -> B \times \beta, where A, B \in Q, a \in T \cup { \eps }, g \in G, and \beta \in G*, F (FinalStates) = set of final states
The transition functions must meet following criteria. Othervise adding conflicting transition will cause exception. $|\delta (q, a, g)| \leq 1$, $\forall q, a, \gamma, q \in Q, a \in (T \cup \varepsilon\}), g \in G.$ if $\delta(q, a, g) \neq \emptyset$, $\delta (q, \varepsilon, h) \neq \emptyset$, then $g \neq h$).
InputSymbolTypeT | used for the terminal alphabet |
PushdownSymbolTypeT | used for the pushdown store alphabet |
StateTypeT | used to the states, and the initial state of the automaton. |
typedef InputSymbolTypeT automaton::SinglePopDPDA< InputSymbolTypeT, PushdownStoreSymbolTypeT, StateTypeT >::InputSymbolType |
typedef PushdownStoreSymbolTypeT automaton::SinglePopDPDA< InputSymbolTypeT, PushdownStoreSymbolTypeT, StateTypeT >::PushdownStoreSymbolType |
typedef StateTypeT automaton::SinglePopDPDA< InputSymbolTypeT, PushdownStoreSymbolTypeT, StateTypeT >::StateType |
|
explicit |
Creates a new instance of the automaton with a concrete set of states, input alphabet, pushdown store alphabet, initial state, initial pushdown symbol and a set of final states.
states | the initial set of states of the automaton |
inputAlphabet | the initial input alphabet |
pushdownStoreAlphabet | the initial set of symbols used in the pushdown store by the automaton |
initialState | the initial state of the automaton |
initialPushdownSymbol | the initial pushdown symbol of the automaton |
finalStates | the initial set of final states of the automaton |
|
explicit |
Creates a new instance of the automaton with a concrete initial state and initial pushdown store symbol.
initialState | the initial state of the automaton |
initialPushdownSymbol | the initial pushdown symbol of the automaton |
|
inline |
Adder of a final state.
state | the new state to be added to a set of final states |
|
inline |
Adder of a input symbol.
symbol | the new symbol to be added to an input alphabet |
|
inline |
Adder of input symbols.
symbols | new symbols to be added to an input alphabet |
|
inline |
Adder of a pushdown store symbol.
symbol | the new symbol to be added to a pushdown store alphabet |
|
inline |
Adder of pushdown store symbols.
symbols | new symbols to be added to a pushdown store alphabet |
|
inline |
Adder of a state.
state | the new state to be added to a set of states |
bool automaton::SinglePopDPDA< InputSymbolType, PushdownStoreSymbolType, StateType >::addTransition | ( | StateType | from, |
common::symbol_or_epsilon< InputSymbolType > | input, | ||
PushdownStoreSymbolType | pop, | ||
StateType | to, | ||
ext::vector< PushdownStoreSymbolType > | push | ||
) |
Adds a transition to the automaton.
The transition is in a form A \times a \times g -> B \times \beta, where A, B \in Q, a \in T \cup { \eps }, g \in G, and \beta \in G*
from | the source state (A) |
input | the input symbol or epsilon (a) |
pop | symbol to be poped from pushdown store on the transition use (g) |
to | the target state (B) |
push | symbols to be pushed to the pushdown store on the transition use (\beta) |
AutomatonException | when transition contains state or symbol not present in the automaton components or when the transition would cause nondeterminism |
bool automaton::SinglePopDPDA< InputSymbolType, PushdownStoreSymbolType, StateType >::addTransition | ( | StateType | from, |
InputSymbolType | input, | ||
PushdownStoreSymbolType | pop, | ||
StateType | to, | ||
ext::vector< PushdownStoreSymbolType > | push | ||
) |
Adds a transition to the automaton.
The transition is in a form A \times a \times g -> B \times \beta, where A, B \in Q, a \in T, g \in G, and \beta \in G*
from | the source state (A) |
input | the input symbol (a) |
pop | symbol to be poped from pushdown store on the transition use (g) |
to | the target state (B) |
push | symbols to be pushed to the pushdown store on the transition use (\beta) |
AutomatonException | when transition contains state or symbol not present in the automaton components or when the transition would cause nondeterminism |
bool automaton::SinglePopDPDA< InputSymbolType, PushdownStoreSymbolType, StateType >::addTransition | ( | StateType | from, |
PushdownStoreSymbolType | pop, | ||
StateType | to, | ||
ext::vector< PushdownStoreSymbolType > | push | ||
) |
Adds a transition to the automaton.
The transition is in a form A \times \eps \times g -> B \times \beta, where A, B \in Q, g \in G, and \beta \in G*
from | the source state (A) |
pop | symbols to be poped from pushdown store on the transition use (g) |
to | the target state (B) |
push | symbols to be pushed to the pushdown store on the transition use (\beta) |
AutomatonException | when transition contains state or symbol not present in the automaton components or when the transition would cause nondeterminism |
|
inline |
Getter of final states.
|
inline |
Getter of final states.
|
inline |
Getter of the initial state.
|
inline |
Getter of the initial state.
|
inline |
Getter of the initial pushdown store symbol.
|
inline |
Getter of the initial pushdown store symbol.
|
inline |
Getter of the input alphabet.
|
inline |
Getter of the input alphabet.
|
inline |
Getter of the pushdown store alphabet.
|
inline |
Getter of the pushdown store alphabet.
|
inline |
Getter of states.
|
inline |
Getter of states.
ext::map< ext::tuple< StateType, common::symbol_or_epsilon< InputSymbolType >, PushdownStoreSymbolType >, ext::pair< StateType, ext::vector< PushdownStoreSymbolType > > > && automaton::SinglePopDPDA< InputSymbolType, PushdownStoreSymbolType, StateType >::getTransitions | ( | ) | && |
Get the transition function of the automaton in its natural form.
const ext::map< ext::tuple< StateType, common::symbol_or_epsilon< InputSymbolType >, PushdownStoreSymbolType >, ext::pair< StateType, ext::vector< PushdownStoreSymbolType > > > & automaton::SinglePopDPDA< InputSymbolType, PushdownStoreSymbolType, StateType >::getTransitions | ( | ) | const & |
Get the transition function of the automaton in its natural form.
|
inline |
The three way comparison implementation
other | the other instance |
other
.
|
inline |
The equality comparison implementation.
other | the other object to compare with. |
|
inline |
Remover of a final state.
state | a state to be removed from a set of final states |
|
inline |
Remover of an input symbol.
symbol | a symbol to be removed from an input alphabet |
|
inline |
Remover of an pushdown store symbol.
symbol | a symbol to be removed from a pushdown store alphabet |
|
inline |
Remover of a state.
state | a state to be removed from a set of states |
bool automaton::SinglePopDPDA< InputSymbolType, PushdownStoreSymbolType, StateType >::removeTransition | ( | const StateType & | from, |
const common::symbol_or_epsilon< InputSymbolType > & | input, | ||
const PushdownStoreSymbolType & | pop, | ||
const StateType & | to, | ||
const ext::vector< PushdownStoreSymbolType > & | push | ||
) |
Removes a transition from the automaton.
The transition is in a form A \times a \times g -> B \times \beta, where A, B \in Q, a \in T \cup { \eps }, g \in G, and \beta \in G*
from | the source state (A) |
input | the input symbol or epsilon (a) |
pop | symbols poped from pushdown store on the transition use (g) |
to | the target state (B) |
push | symbols pushed to the pushdown store on the transition use (\beta) |
AutomatonException | when removed transition left hand side was found but the right hand side did not match. |
bool automaton::SinglePopDPDA< InputSymbolType, PushdownStoreSymbolType, StateType >::removeTransition | ( | const StateType & | from, |
const InputSymbolType & | input, | ||
const PushdownStoreSymbolType & | pop, | ||
const StateType & | to, | ||
const ext::vector< PushdownStoreSymbolType > & | push | ||
) |
Removes a transition from the automaton.
The transition is in a form A \times a \times g -> B \times \beta, where A, B \in Q, a \in T, g \in G, and \beta \in G*
from | the source state (A) |
input | the input symbol (a) |
pop | symbols poped from pushdown store on the transition use (g) |
to | the target state (B) |
push | symbols pushed to the pushdown store on the transition use (\beta) |
AutomatonException | when removed transition left hand side was found but the right hand side did not match. |
bool automaton::SinglePopDPDA< InputSymbolType, PushdownStoreSymbolType, StateType >::removeTransition | ( | const StateType & | from, |
const PushdownStoreSymbolType & | pop, | ||
const StateType & | to, | ||
const ext::vector< PushdownStoreSymbolType > & | push | ||
) |
Removes a transition from the automaton.
The transition is in a form A \times \eps \times g -> B \times \beta, where A, B \in Q, g \ in G, and \beta \in G*
from | the source state (A) |
pop | symbols poped from pushdown store on the transition use (g) |
to | the target state (B) |
push | symbols pushed to the pushdown store on the transition use (\beta) |
AutomatonException | when removed transition left hand side was found but the right hand side did not match. |
|
inline |
Setter of final states.
states | completely new set of final states |
|
inline |
Setter of the initial state.
state | new initial state of the automaton |
|
inline |
Setter of the initial pushdown store symbol.
symbol | new initial pushdown store symbol of the automaton |
|
inline |
Setter of input alphabet.
symbols | completely new input alphabet |
|
inline |
Setter of a pushdown store alphabet.
symbols | completely new pushdown store alphabet |
|
inline |
Setter of states.
states | completely new set of states |
|
friend |
Print this object as raw representation to ostream.
out | ostream where to print |
instance | object to print |