| dbo:abstract
|
- In formal language theory, the Chomsky–Schützenberger representation theorem is a theorem derived by Noam Chomsky and Marcel-Paul Schützenberger about representing a given context-free language in terms of two simpler languages. These two simpler languages, namely a regular language and a Dyck language, are combined by means of an intersection and a homomorphism. A few notions from formal language theory are in order. A context-free language is regular, if can be described by a regular expression, or, equivalently, if it is accepted by a finite automaton. A homomorphism is based on a function which maps symbols from an alphabet to words over another alphabet ; If the domain of this function is extended to words over in the natural way, by letting for all words and , this yields a homomorphism . A matched alphabet is an alphabet with two equal-sized sets; it is convenient to think of it as a set of parentheses types, where contains the opening parenthesis symbols, whereas the symbols in contains the closing parenthesis symbols. For a matched alphabet , the Dyck language is given by Chomsky–Schützenberger theorem. A language L over the alphabet is context-free if and only if there exists
* a matched alphabet
* a regular language over ,
* and a homomorphism such that . Proofs of this theorem are found in several textbooks, e.g. or . (en)
- En informatique théorique, et notamment en théorie des langages formels, le théorème de Chomsky-Schützenberger est un théorème de représentation. Il affirme que tout langage algébrique peut s'exprimer, au moyen d'une certaine construction, à partir d'un langage de Dyck. En ce sens, le théorème affirme que les langages de Dyck sont des langages algébriques « typiques ». Ce théorème est nommé ainsi d'après Noam Chomsky et Marcel-Paul Schützenberger. Il figure dans leur article commun de 1963. (fr)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 3381 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdfs:comment
|
- En informatique théorique, et notamment en théorie des langages formels, le théorème de Chomsky-Schützenberger est un théorème de représentation. Il affirme que tout langage algébrique peut s'exprimer, au moyen d'une certaine construction, à partir d'un langage de Dyck. En ce sens, le théorème affirme que les langages de Dyck sont des langages algébriques « typiques ». Ce théorème est nommé ainsi d'après Noam Chomsky et Marcel-Paul Schützenberger. Il figure dans leur article commun de 1963. (fr)
- In formal language theory, the Chomsky–Schützenberger representation theorem is a theorem derived by Noam Chomsky and Marcel-Paul Schützenberger about representing a given context-free language in terms of two simpler languages. These two simpler languages, namely a regular language and a Dyck language, are combined by means of an intersection and a homomorphism. Chomsky–Schützenberger theorem. A language L over the alphabet is context-free if and only if there exists
* a matched alphabet
* a regular language over ,
* and a homomorphism such that . (en)
|
| rdfs:label
|
- Chomsky–Schützenberger representation theorem (en)
- Théorème de Chomsky-Schützenberger (langage formel) (fr)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
