# Tag Info

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