Register

GO Classes DPP | GATE CS | Theory of Computation | Decidability

ago
34 views
0 0 votes

Given an NFA $N$, we want to decide efficiently whether $$L(N)\cap 0^*=\varnothing$$ Which method is appropriate?

  1. Convert $N$ to a DFA, take a product with a DFA for $0^*$, and then run the DFA-emptiness algorithm.
     
  2. Convert $N$ to a regular expression and check whether the expression contains the symbol $1$.
     
  3. Remove all transitions that read symbols other than $0$, then check whether the start state can reach an accepting state.
     
  4. The problem is NP-hard, so no efficient algorithm should be expected.

1 Answer

0 0 votes

We only care about strings belonging to

$0^*=\{\epsilon,0,00,000,\ldots\}$.

Therefore any transition consuming a symbol other than $0$ is irrelevant.

Delete those transitions from $N$. Call the resulting NFA $N'$.

Now, $L(N)\cap 0^*\neq\varnothing$

exactly when some accepting state of $N'$ is reachable from its start state.

So we only need a graph-reachability search.

That is polynomial and avoids the potentially exponential NFA-to-DFA subset construction in A.

Therefore,

Answer : $\boxed{\mathrm{C}}$

ago
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

0 0 votes
1 1 answer
34
34 views
GO Classes asked 2 days ago
34 views
GO Classes DPP | GATE CS | Theory of Computation | Decidability
Let, $A_{\mathrm{DFA}}=\{\langle D,w\rangle\mid D\ \mathrm{accepts}\ w\}$,$E_{\mathrm{DFA}}=\{\langle D\rangle\mid L(D)=\varnothing\}$,and$EQ_{\mathrm{DFA}}=\{\langle D_1...
0 0 votes
1 1 answer
63
63 views
GO Classes asked 2 days ago
63 views
GO Classes DPP | GATE CS | Theory of Computation | Church-Turing Thesis
Which statement is captured by the Church-Turing thesis?Every yes/no decision problem is decidable. The thesis specifically states that some decision problems are neither...
0 0 votes
1 1 answer
33
33 views
GO Classes asked 2 days ago
33 views
GO Classes DPP | GATE CS | Theory of Computation | Decision Problem
Consider the language corresponding to the problem of recognizing binary palindromes: $$L=\{w\in\{0,1\}^*\mid w=w^R\}$$ Which statement is correct?$L$ is regular and deci...
0 0 votes
1 1 answer
38
38 views
GO Classes asked 2 days ago
38 views
GO Classes DPP | GATE CS | Theory of Computation | Encoding Finite Objects
Consider algorithms for the following tasks:Recognizing palindromes Reversing a string Recognizing Pythagorean triples Computing $\mathrm{gcd}$ of two positive integers T...