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
Can v find the given number is palindrome or not using turing machine

We'll close our consideration of regular languages by looking at whether (certain) problems about regular languages are algorithmically decidable.

This close relationship between the SL2 languages and the recognizable languages lets us use some of what we know about SL 2 to discover properties of the recognizable languages.

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

build a TM that enumerate even set of even length string over a

The computation of an SL 2 automaton A = ( Σ, T) on a string w is the maximal sequence of IDs in which each sequential pair of IDs is related by |- A and which starts with the in

I want a proof for any NP complete problem

We have now de?ned classes of k-local languages for all k ≥ 2. Together, these classes form the Strictly Local Languages in general. De?nition (Strictly Local Languages) A langu

The path function δ : Q × Σ*→ P(Q) is the extension of δ to strings: Again, this just says that to ?nd the set of states reachable by a path labeled w from a state q in an