New answers tagged nondeterminism
0
There are several alternatives for the definition of a PDA, all of which are equivalent, in the sense that computationally they specify the same class of languages. To answer your question, you can perhaps take a look at the precise definition of PDAs you are working with.
For the following, with $X_\varepsilon$ I mean $X\cup\{\varepsilon\}$.
Some ...
-1
A PDA (including a NPDA) can only move if there is a symbol on the top of the stack, the possible moves depend on the current state, the symbol on the top of the stack and the input symbol (or $\epsilon$). No stack, no further moves possible.
0
if I want to design a NFA (that's NOT A DFA) that accepts the set of all strings that do not contain the substring 1010, is this correct? because I can just accept 1010 by capturing it in the starting state itself, right?
Your machine is not correct. The problem is as you pointed out: If you start in state $S$ of your machine, you can take the string 1010 ...
1
Could someone explain to me why we need such multiple options? I would never expect to encounter something uncertainty in the implementation of an algorithm.
I think this is your primary misconception: an NTM is not supposed to be a realistic machine. That is, no one has ever tried to build a NTM, no one knows how to implement it, and algorithms in the real ...
0
From S with input 1, you can’t go both to state S and A. In states A, B, C where do you go with the other input? What happens in state D if you get further input?
4
You can use either way. In both cases you construct a mapping from the states of the automaton to regular expressions, $[-]: Q\to RE$.
Let $(s, l, t)$ denote a transition from $s$ with label $l$ to target state $t$.
Also, let $\oplus_{i\leq n}r_i = r_1 + \ldots + r_n$.
1st case: By incoming edges.
Add a final state, $F$, and an $\varepsilon$-transition ...
1
If they can only move the head right, they are equivalent to finite automata.
Top 50 recent answers are included
