Emptiness problem, Theory of Computation

Assignment Help:

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.


Related Discussions:- Emptiness problem

Algorithm, What is the Best way to write algorithm and construct flow chart...

What is the Best way to write algorithm and construct flow chart? What is Computer? How to construct web page and Designe it?

Venkatesh, What is the arbwnememmsmdbdbfbfjmfksmjejfnfnfnnrndmnfjfjfnrnkrkf...

What is the arbwnememmsmdbdbfbfjmfksmjejfnfnfnnrndmnfjfjfnrnkrkfjfnfmkrjrbfbbfjfnfjruhrvrjkgktithhrbenfkiffnbr ki rnrjjdjrnrk bd n FBC..jcb?????????????????????????????????????????

Equivalence of nfas and dfas, In general non-determinism, by introducing a ...

In general non-determinism, by introducing a degree of parallelism, may increase the accepting power of a model of computation. But if we subject NFAs to the same sort of analysis

Computation of an automaton, The computation of an SL 2 automaton 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

REGULAR GRAMMAR, Find the Regular Grammar for the following Regular Express...

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

Automata, As we are primarily concerned with questions of what is and what ...

As we are primarily concerned with questions of what is and what is not computable relative to some particular model of computation, we will usually base our explorations of langua

Xx, Ask queyystion #Minimum 100 words accepted#

Ask queyystion #Minimum 100 words accepted#

Concatenation, We saw earlier that LT is not closed under concatenation. If...

We saw earlier that LT is not closed under concatenation. If we think in terms of the LT graphs, recognizing the concatenation of LT languages would seem to require knowing, while

Qbasic, Ask question #Minimum 100 words accepte

Ask question #Minimum 100 words accepte

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd