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


Theorem (Myhill-Nerode) A language L ⊆ Σ is recognizable iff ≡L partitions Σ* into ?nitely many Nerode equivalence classes. Proof: For the "only if" direction (that every recogn

#can you solve a problem of palindrome using turing machine with explanation and diagrams?

Find the Regular Grammar for the following Regular Expression:                    a(a+b)*(ab*+ba*)b.

Claim Under the assumptions above, if there is an algorithm for checking a problem then there is an algorithm for solving the problem. Before going on, you should think a bit about

We got the class LT by taking the class SL and closing it under Boolean operations. We have observed that LT ⊆ Recog, so certainly any Boolean combination of LT languages will also


Let ? ={0,1} design a Turing machine that accepts L={0^m 1^m 2^m } show using Id that a string from the language is accepted & if not rejected .

i have some questions in automata, can you please help me in solving in these questions?