New answers tagged automata-theory
5
This model is one of the standard models in automata theory and it has been examined by some researchers.
The references given in the first comment are very good starting points.
When the head is two-way, the classes of languages recognized by such models are identical to logarithmic-space classes. However, when the head is one-way, then, up to my ...
2
Can we have more than one Deterministic Finite Automata (DFA) diagrams for a set of strings?
Of course!
There's also an algorithm to minimize a deterministic finite automata into a minimal deterministic finite automata. The existence of such algorithm is a proof that for most, if not all, sets of strings, many DFAs can be defined.
2
In the standard $\epsilon$-free PDA definition the transition function is:
$\sigma : Q \times \Sigma \times \Gamma \to Q \times \Gamma^*$
$(q_i, a, A, q_j, \alpha) \in \sigma$ means that the PDA on state $q_i$, with head on input $a$ and $A \in \Gamma$ on top of the stack, enters state $q_j$ and replace $A$ with $\alpha \in \Gamma^*$
According to this ...
Top 50 recent answers are included
