The equivalence and inclusion problems for NTS languages (Q1083219)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: The equivalence and inclusion problems for NTS languages |
scientific article; zbMATH DE number 3976372
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The equivalence and inclusion problems for NTS languages |
scientific article; zbMATH DE number 3976372 |
Statements
The equivalence and inclusion problems for NTS languages (English)
0 references
1985
0 references
A context-free grammar is said to be NTS if the set of sentential forms it generates is unchanged when the rules are used both ways. We prove that this class of grammars has a decidable equivalence problem. Then we show that one can decide whether a given c.f. grammar is NTS or not. We prove that the class of NTS grammars has an undecidable inclusion problem.
0 references
context-free grammar
0 references
decidable equivalence problem
0 references
NTS grammars
0 references
undecidable inclusion problem
0 references
0 references
