In theoretical computer science and formal language theory, a formal language is empty if its set of valid sentences is the empty set. The emptiness problem is the question of determining whether a language is empty given some representation of it, such as a finite-state automaton. For an automaton having states, this is a decision problem that can be solved in time. However, variants of that question, such as the emptiness problem for non-erasing stack automata, are PSPACE-complete.
| Attributes | Values |
|---|
| rdfs:label
| - Leerheitsproblem (de)
- Emptiness problem (en)
|
| rdfs:comment
| - Als Leerheitsproblem bezeichnet man in der theoretischen Informatik das Problem, zu entscheiden, ob eine in Form einer formalen Grammatik gegebene formale Sprache leer ist, also , oder nicht. Das Problem ist also, herauszufinden, ob es Wörter gibt, die den Regeln der Grammatik genügen, oder nicht. Die Entscheidbarkeit des Leerheitsproblems hängt von der Komplexität der zugrundeliegenden Grammatik ab: Für die Grammatiken vom Typ 2 oder höher in der Chomsky-Hierarchie ist das Leerheitsproblem entscheidbar, für die Grammatiken bis Typ 1 im Allgemeinen jedoch nicht. (de)
- In theoretical computer science and formal language theory, a formal language is empty if its set of valid sentences is the empty set. The emptiness problem is the question of determining whether a language is empty given some representation of it, such as a finite-state automaton. For an automaton having states, this is a decision problem that can be solved in time. However, variants of that question, such as the emptiness problem for non-erasing stack automata, are PSPACE-complete. (en)
|
| dct:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - Als Leerheitsproblem bezeichnet man in der theoretischen Informatik das Problem, zu entscheiden, ob eine in Form einer formalen Grammatik gegebene formale Sprache leer ist, also , oder nicht. Das Problem ist also, herauszufinden, ob es Wörter gibt, die den Regeln der Grammatik genügen, oder nicht. Die Entscheidbarkeit des Leerheitsproblems hängt von der Komplexität der zugrundeliegenden Grammatik ab: Für die Grammatiken vom Typ 2 oder höher in der Chomsky-Hierarchie ist das Leerheitsproblem entscheidbar, für die Grammatiken bis Typ 1 im Allgemeinen jedoch nicht. (de)
- In theoretical computer science and formal language theory, a formal language is empty if its set of valid sentences is the empty set. The emptiness problem is the question of determining whether a language is empty given some representation of it, such as a finite-state automaton. For an automaton having states, this is a decision problem that can be solved in time. However, variants of that question, such as the emptiness problem for non-erasing stack automata, are PSPACE-complete. The emptiness problem is undecidable for context-sensitive grammars, a fact that follows from the undecidability of the halting problem. It is, however, decidable for context-free grammars. (en)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)