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
DEGENERATE OF THE INITIAL SOLUTION

The fact that the Recognition Problem is decidable gives us another algorithm for deciding Emptiness. The pumping lemma tells us that if every string x ∈ L(A) which has length grea

how many pendulum swings will it take to walk across the classroom?

Generate 100 random numbers with the exponential distribution lambda=5.0.What is the probability that the largest of them is less than 1.0?

In Exercise 9 you showed that the recognition problem and universal recognition problem for SL2 are decidable. We can use the structure of Myhill graphs to show that other problems

Differentiate between DFA and NFA. Convert the following Regular Expression into DFA. (0+1)*(01*+10*)*(0+1)*. Also write a regular grammar for this DFA.

i want to do projects for theory of computation subject what topics should be best.

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


The universe of strings is a very useful medium for the representation of information as long as there exists a function that provides the interpretation for the information carrie