Emptiness problem, Theory of Computation

The Emptiness Problem is the problem of deciding if a given regular language is empty (= ∅).

Theorem 4 (Emptiness) The Emptiness Problem for Regular Languages is decidable.

Proof: We'll sketch three different algorithms for deciding the Emptiness Problem, given some DFA A = (Q,Σ, T, q0, F).

(Emptiness 1) A string w is in L(A) iff it labels a path through the transition graph of A from q0 to an accepting state. Thus, the language will be non-empty iff there is some such path. So the question of Emptiness reduces to the question of connectivity: the language recognized by A is empty iff there is no accepting state in the connected component of its transition graph that is rooted at q0. The problem of determining connected components of directed graphs is algorithmically solvable,by Depth-First Search, for instance (and solvable in time linear in the number of nodes). So, given A, we just do a depth-?rst search of the transition graph rooted at the start state keeping track of whether we encounter any accepting state. We return "True" iff we ?nd none.

Posted Date: 3/21/2013 1:51:00 AM | Location : United States







Related Discussions:- Emptiness problem, Assignment Help, Ask Question on Emptiness problem, Get Answer, Expert's Help, Emptiness problem Discussions

Write discussion on Emptiness problem
Your posts are moderated
Related Questions
conversion from nfa to dfa 0 | 1 ___________________ p |{q,s}|{q} *q|{r} |{q,r} r |(s) |{p} *s|null |{p}


The initial ID of the automaton given in Figure 3, running on input ‘aabbba' is (A, aabbba) The ID after the ?rst three transitions of the computation is (F, bba) The p

And what this money. Invovle who it involves and the fact of,how we got itself identified candidate and not withstanding time date location. That shouts me media And answers who''v

You are required to design a system that controls the speed of a fan's rotation. The speed at which the fan rotates is determined by the ambient temperature, i.e. as the temperatur

A common approach in solving problems is to transform them to different problems, solve the new ones, and derive the solutions for the original problems from those for the new ones


Suppose G = (N, Σ, P, S) is a reduced grammar (we can certainly reduce G if we haven't already). Our algorithm is as follows: 1. Define maxrhs(G) to be the maximum length of the

A problem is said to be unsolvable if no algorithm can solve it. The problem is said to be undecidable if it is a decision problem and no algorithm can decide it. It should be note

We will specify a computation of one of these automata by specifying the pair of the symbols that are in the window and the remainder of the string to the right of the window at ea