New answers tagged nondeterminism
3
votes
Translating non-deterministic finite automata with counters to deterministic ones
Yes, they can be employed in a straightforward way. However, the size of the formulas blows up exponentially big.
Let $\ell_{s \to t}$ denote the formula on the NFA transition from $s$ to $t$. For ...

D.W.♦
- 154k
0
votes
Dangling else determinism
As pointed by @Pseudonym a context-free language is deterministic if and only if it has a grammar such that is $LR(k)$, for some $k$.
Let's take $k = 1$, the grammar is $LR(1)$ (and $LALR(1)$) so it ...
Top 50 recent answers are included
Related Tags
nondeterminism × 388finite-automata × 141
automata × 104
turing-machines × 85
complexity-theory × 81
formal-languages × 40
pushdown-automata × 38
regular-languages × 26
algorithms × 25
context-free × 23
time-complexity × 21
np × 21
space-complexity × 21
computation-models × 21
regular-expressions × 13
polynomial-time × 13
closure-properties × 12
computability × 11
terminology × 10
satisfiability × 9
np-complete × 8
reference-request × 8
complexity-classes × 8
simulation × 8
halting-problem × 7