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

TRANSPORTATION, DEGENERATE OF THE INITIAL SOLUTION

DEGENERATE OF THE INITIAL SOLUTION

#titl, matlab v matlab

matlab v matlab

Algorithm for the universal recognition problem, Sketch an algorithm for th...

Sketch an algorithm for the universal recognition problem for SL 2 . This takes an automaton and a string and returns TRUE if the string is accepted by the automaton, FALSE otherwi

what is a turing machine, A Turing machine is a theoretical computing mach...

A Turing machine is a theoretical computing machine made-up by Alan Turing (1937) to serve as an idealized model for mathematical calculation. A Turing machine having of a line of

Operator p, implementation of operator precedence grammer

implementation of operator precedence grammer

Shell script, shell script to print table in given range

shell script to print table in given range

Formal languages and grammar, The universe of strings is a very useful medi...

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

Powerset construction, As de?ned the powerset construction builds a DFA wit...

As de?ned the powerset construction builds a DFA with many states that can never be reached from Q′ 0 . Since they cannot be reached from Q′ 0 there is no path from Q′ 0 to a sta

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