Emptiness problem

As emptiness problem is known in theoretical computer science problem to decide whether in the form of a formal grammar given formal language is empty, so no, or. So the problem is figuring out whether or not there are words that conform to the rules of grammar. ${\ displaystyle L}$ ${\ displaystyle L = \ emptyset}$

The decidability of the emptiness problem depends on the complexity of the underlying grammar: for grammars of type 2 or higher in the Chomsky hierarchy the emptiness problem is decidable, for grammars up to type 1, however, in general not.

Emptiness problem for finite automata

A (non-) deterministic finite automaton A is given. It is to be decided whether the formal language is or not. ${\ displaystyle L (A) = \ emptyset}$

We are looking for an algorithm to solve the emptiness problem.

Naive approach

One checks all words w (with length ≤ number of states of the automaton), whether they are recognized by A. If a word is recognized, then ≠ applies , otherwise the language is empty. ${\ displaystyle L (A)}$ ${\ displaystyle \ emptyset}$

The approach cannot be used in practice for alphabets with more than one symbol and larger automata - the time required is exponential ( ). ${\ displaystyle {\ mathcal {O}} (2 ^ {n})}$

Marking algorithm

The marking algorithm regards a finite automaton as a directed graph G = (Q, E). Q elements are called nodes and E elements are called edges. If a word w exists in L (A), there is a path from the start state to the end state, the automaton. It is now checked whether a marked state of the graph is an end state of the machine.

Beginning with the starting state p1: p1 is marked and added to the list of marked states. It is then checked which states can be reached by p1. Mark these states and add p2, p3 ... to the list and delete p1 from the list. This is repeated until all the states to be reached are marked and the queue is empty. If no end state is reached (and therefore not marked), the language is empty.

The algorithm adds each node to the list a maximum of once and marks it. Thus, the algorithm terminates in the time required by n².

Grammar emptiness problem

In the case of the emptiness problem for a grammar G, the question is whether or not G creates an empty language.

Solution using the marking algorithm: The symbols of the rules from which a terminal word can be derived are marked. If the start symbol is marked, the language is not empty.

Emptiness problem

contents