25
votes
Is it mandatory to define transitions on every possible alphabet in Deterministic Finite Automata?
Suppose a DFA was allowed to have missing transitions. What happens if you encounter a symbol which has no transtion defined for it? The result is undefined. That would seem to violate the "...
- 642
24
votes
Accepted
Why NFA is called Non-deterministic?
"Deterministic" means "if you put the system in the same situation twice, it is guaranteed to make the same choice both times".
"Non-deterministic" means "not deterministic", or in other words, "if ...
D.W.♦
- 166k
19
votes
Probabilistic methods for undecidable problem
So, we have a TM $M$ that can in addition flip a fair coin. We have the promise that for every input $M$ will eventually halt and give an answer, no matter what the coin results are. Moreover, we ...
- 3,293
13
votes
Accepted
Is it mandatory to define transitions on every possible alphabet in Deterministic Finite Automata?
A DFA is specified by the following data:
An alphabet $\Sigma$.
A set of states $Q$.
An initial state $q_0 \in Q$.
A set of final states $F \subseteq Q$.
A transition function $\delta\colon Q \times \...
- 279k
13
votes
Accepted
Incorrect proof of closure under the star operation using NFA results in the NFA recognizing undesired strings?
Consider a two state automaton for the language $a^*b$, two transitions from the initial state, one looping with label $a$, the other with label $b$ to the final state.
Making the initial state final,...
- 31.1k
13
votes
Accepted
Why nondeterminism?
Excellent question! Nondeterminism first appears (so it seems) in a classical paper of Rabin and Scott, Finite automata and their decision problems, in which the authors first describe finite automata ...
- 279k
11
votes
Accepted
$\mathsf{NL}$ versus $\mathsf{NL}[2]$
You can show that $\mathsf{NL}[2] \subseteq \mathsf{NL}$ as follows. We are given an $\mathsf{NL}[2]$ machine $M$, and we want to simulate it with an $\mathsf{NL}$ machine $M'$. The first that $M$ ...
- 279k
10
votes
Accepted
Does the smallest DFA equivalent to this NFA requires at least $O(2^n)$ state?
The NFA accepts strings where the fourth letter from the end is 1. Your DFA doesn't accept 11000.
A DFA doesn't know how much input is left, so the property "the fourth character from the end" is ...
- 5,981
10
votes
How does a nondeterministic Turing machine work?
Here are several ways of thinking about non-determinism (copied from this answer).
The genie. Whenever the machine has a choice, a genie tells it which way to go. If the input is in the language, ...
- 279k
10
votes
Why NFA is called Non-deterministic?
Take this automaton for instance, it's an NFA and it accepts the string $0110$. To be more pedantic, it accepts strings that end in $10$.
To see that we just need to check whether it reaches an ...
- 1,493
9
votes
Accepted
Non-deterministic Finite Automata | Sipser Example 1.16
You are confusing $\epsilon$ with a letter. It's not a letter! It's just the empty string.
Let us consider a slightly more general model, "word-NFA". A word-NFA is like an NFA, but each transition is ...
- 279k
8
votes
Does the smallest DFA equivalent to this NFA requires at least $O(2^n)$ state?
You can prove the lower bound on the number of states using Myhill-Nerode theory.
Suppose that we are given a language $L$, in this case the language over $\{0,1\}$ of words in which the $n$th last ...
- 279k
8
votes
Notation in NFA, DFA diagrams and language
You need to distinguish between three kinds of operations:
Operations on numbers such as 0 and 1. $0^3 = 0$ when $0$ is taken to be a number. Here, $0^3 = 0 ⋅ 0 ⋅ 0$, where $⋅$ is integer ...
- 5,941
7
votes
Accepted
Equivalence between alternative definitions of NP
The definition of $\text{NP}$ in terms of verification can be formally stated as follows:
A language $L$ is in $\text{NP}$ if there exists a polynomial verifier for $L$ such that for every $x$:
$$...
- 9,631
7
votes
Do NPDA work in parallel?
That's not how non-determinism works, though perhaps it's how you'd simulate it in real life. Here are several ways of thinking about non-determinism.
The genie. Whenever the machine has a choice, a ...
- 279k
7
votes
Accepted
Do NPDA work in parallel?
The difference between DPDA and NPDA is that in NPDA there may be more than one possible transition from a single state given input symbol and stack symbol, while in a DPDA there is only one ...
- 9,885
7
votes
How does a nondeterministic Turing machine work?
The difference between deterministic and non-deterministic Turing machines lies in the transition function. In deterministic Turing machines $\delta$ the transition function is a partial function:
$\...
- 2,204
7
votes
Accepted
motivation and idea of defining non-deterministic Turing machine
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 ...
- 7,248
7
votes
Accepted
Show $L = $ { w $\in (a,b) ^* $| for every u substring of w, $-5\le|u|_a−|u|_b\le5\}$ is regular
Nice question! This is a very nontrivial problem involving regular languages.
First of all: no, you cannot run an automaton on every substring of a string skipping other letters, you are supposed to ...
- 954
7
votes
Accepted
What role does the lower bound play in the statement of Savitch's Theorem?
The proof relies on the following property: the time-complexity of a decider machine is at most exponential in its space-complexity. The bound assumptions, namely $f(n)\geq \log n$, are sufficient ...
- 4,874
6
votes
How to prove: If $\textsf{EXP} \subseteq \textsf{P/poly} $ then $\textsf{EXP} = \Sigma^p_2$
There is a more 'elementary' proof of the problem that doesn't involve the polynomial-encoding/self-correction ideas of BFL. The result appears in the original Karp-Lipton paper and is credited to ...
- 161
6
votes
Is it mandatory to define transitions on every possible alphabet in Deterministic Finite Automata?
A DFA is often defined as a restricted type of NFA. If $\Sigma$ is the input alphabet and $Q$ is the set of states, the transition structure of an NFA is specified as either a relation $\rho \...
- 171
6
votes
Accepted
Understanding why ALL_nfa is in co-nspace
To show that $ALL_{\mathsf{NFA}}$ is in $\mathrm{co-NSPACE}(n)$, we must show that the complement $\overline{ALL_{\mathsf{NFA}}}$ is in $\mathrm{NSPACE}(n)$.
The complement is
$$\overline{ALL_{\...
- 2,516
6
votes
Accepted
Why we can't use non-deterministic turing machines in this case?
Your reasoning is not wrong. But recall that decidability requires TM machine halt with YES if $\exists w \text{ such that } w^4 \in L(G)$ or NO if $\nexists w \text{ such that }w^4 \in L(G)$. In ...
- 9,885
6
votes
How does a nondeterministic Turing machine work?
Augmentation with a guessing module.
I found this model in "Computers and Intractability" by M.R. Garey and D.S. Johnson.
The NDTM has exactly the same structure as a DTM, except that it is
...
- 9,885
6
votes
Why NFA is called Non-deterministic?
The transition function of an NFA specifies the allowed transitions at any point in time. There could be more than one option, and the NFA chooses a transition nondeterministically with the goal of ...
- 279k
6
votes
What is difference between nondeterministic polynomial time and exponential time?
Every nondeterministic polynomial time algorithm can be converted to an exponential time algorithm, where exponential means $O(e^{n^C})$ for some constant $C$. The converse probably doesn't hold.
- 279k
6
votes
Accepted
Minimal number of states for an NFA of all different words
Here is a matching $\Omega(k^2)$ lower bound.
Consider any NFA for your language. Let $Q_i$ be the set of states $q$ such that:
There is some word $w$ of length $i$ such that the NFA could be at ...
- 279k
6
votes
Accepted
When converting a epsilon NFA to NFA to DFA, how to handle the start state?
There is no need to apply the $\varepsilon$-closure twice when computing transitions. There are two main ways to convert an $\varepsilon$-NFA into a NFA: the forward closure and the backward closure. ...
- 16.9k
Only top scored, non community-wiki answers of a minimum length are eligible