On equality of multiplicity sets of regular languages (Q1087336)
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: On equality of multiplicity sets of regular languages |
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On equality of multiplicity sets of regular languages |
scientific article |
Statements
On equality of multiplicity sets of regular languages (English)
0 references
1985
0 references
Every nondeterministic finite automaton A defines a set of naturals \(M_ A\) as follows: n belongs to \(M_ A\) iff there exists a word w such that A accepts w just by n ways. The set \(M_ A\) is called ''the multiplicity set of the regular languages L(A)''. The main theorem is that there is no algorithm deciding, given two finite automata A and B, equality of \(M_ A\) and \(M_ B\).
0 references
equivalence problem for multiplicity sets of regular languages
0 references
nondeterministic finite automaton
0 references
0 references
