In the theory of formal languages, the Myhill–Nerode theorem provides a necessary and sufficient condition for a language to be regular. The theorem is named for John Myhill and Anil Nerode, who proved it at the University of Chicago in 1958.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Myhillova–Nerodova věta (cs)
- Satz von Myhill-Nerode (de)
- Théorème de Myhill-Nerode (fr)
- Teorema di Myhill-Nerode (it)
- マイヒル–ネローデの定理 (ja)
- Myhill–Nerode theorem (en)
- Stelling van Myhill-Nerode (nl)
- Twierdzenie Myhilla-Nerode’a (pl)
- Teorema de Myhill-Nerode (pt)
- Теорема Майхилла — Нероуда (ru)
- 迈希尔－尼罗德定理 (zh)
|
| rdfs:comment
| - Nerodova věta popisuje regulární jazyky, když říká, že formální jazyk nad konečnou abecedou je regulární, právě když „dělí“ množinu všech slov nad danou abecedou na konečně mnoho podtříd s určitými vlastnostmi (popsanými dále v textu).Myhillova-Nerodova věta je rozšířením Nerodovy věty o část týkající se prefixové ekvivalence. (cs)
- In the theory of formal languages, the Myhill–Nerode theorem provides a necessary and sufficient condition for a language to be regular. The theorem is named for John Myhill and Anil Nerode, who proved it at the University of Chicago in 1958. (en)
- マイヒル–ネローデの定理（英: Myhill–Nerode theorem）とは、ある形式言語が正規言語であるための必要十分条件を提示した定理である。ほとんどの場合、ある言語が正規言語でないことを証明するのに使われる。 名称は1958年にこの定理を発見したシカゴ大学の John Myhill と Anil Nerode が由来である。 (ja)
- Nella teoria dei linguaggi formali il teorema di Myhill-Nerode fornisce una condizione necessaria e sufficiente per stabilire se un linguaggio sia regolare o meno. Secondo il teorema di Myhill-Nerode, ogni linguaggio regolare sull'alfabeto consiste nell'unione di classe di equivalenza di una relazione invariante a destra di indice finito sulla chiusura di Kleene di . (it)
- De stelling van Myhill-Nerode geeft een noodzakelijke en voldoende voorwaarde die aangeeft wanneer een formele taal regulier is. De stelling luidt, dat een formele taal regulier is, dan en slechts dan als haar Myhill-Nerode-equivalentie eindig veel equivalentieklassen heeft. De stelling werd genoemd naar de wiskundigen en , die haar in 1958 voor het eerst bewezen. (nl)
- Twierdzenie Myhilla-Nerode’a – twierdzenie w teorii języków formalnych podające konieczne i dostateczne warunki na to, by dany język był regularny. Zostało udowodnione w 1958 roku przez Johna Myhilla i . (pl)
- В теории формальных языков теорема Майхилла — Нероуда определяет необходимое и достаточное условия регулярности языка. Теорема названа в честь Джона Майхилла и Энила Нероуда, доказавших её в Чикагском университете в 1958 году. (ru)
- Acerca da teoria de Linguagens Formais, o Teorema de Myhill-Nerode fornece uma condição necessária e suficiente para que uma linguagem seja regular. O nome do teorema refere-se a John Myhill e , que o provaram na Universidade de Chicago em 1958. (pt)
- 在形式语言理论中，Myhill–Nerode 定理提供了一个语言是正则语言的必要和充分条件。它近乎专门的被用来证明一个给定语言不是正则的。 这个定理得名于 和 ，他们于1958年在芝加哥大学证明了这个定理。 (zh)
- Der Satz von Myhill-Nerode gibt im Fachgebiet Formale Sprachen der Theoretischen Informatik ein notwendiges und hinreichendes Kriterium dafür an, dass eine formale Sprache regulär ist. Er wurde im Jahr 1957/1958 von John Myhill und Anil Nerode vorgestellt und bewiesen. (de)
- En informatique théorique, et notamment en théorie des langages formels et des automates, le théorème de Myhill-Nerode donne une condition nécessaire et suffisante pour qu'un langage formel soit un langage rationnel, c'est-à-dire reconnaissable par un automate fini. Ce théorème porte les noms de John Myhill et Anil Nerode qui l'ont prouvé en 1958. (fr)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - Der Satz von Myhill-Nerode gibt im Fachgebiet Formale Sprachen der Theoretischen Informatik ein notwendiges und hinreichendes Kriterium dafür an, dass eine formale Sprache regulär ist. Er wurde im Jahr 1957/1958 von John Myhill und Anil Nerode vorgestellt und bewiesen. Umgangssprachlich ausgedrückt dient der Satz hauptsächlich dazu, herauszufinden, ob eine formale Sprache so „gutartig“ oder „einfach gestrickt“ ist, dass ein Computer mit konstantem Speicher (d. h. mit endlich begrenztem Speicher, dessen Größe nicht von der Eingabe abhängt) automatisch feststellen kann, ob eine Zeichenfolge ein Wort der Sprache ist oder nicht. (de)
- Nerodova věta popisuje regulární jazyky, když říká, že formální jazyk nad konečnou abecedou je regulární, právě když „dělí“ množinu všech slov nad danou abecedou na konečně mnoho podtříd s určitými vlastnostmi (popsanými dále v textu).Myhillova-Nerodova věta je rozšířením Nerodovy věty o část týkající se prefixové ekvivalence. (cs)
- En informatique théorique, et notamment en théorie des langages formels et des automates, le théorème de Myhill-Nerode donne une condition nécessaire et suffisante pour qu'un langage formel soit un langage rationnel, c'est-à-dire reconnaissable par un automate fini. Ce théorème porte les noms de John Myhill et Anil Nerode qui l'ont prouvé en 1958. L'intérêt de cet énoncé est que la condition nécessaire et suffisante porte sur le langage lui-même, et ne fait pas appel à la construction d'un automate. La preuve est par contre constructive, et permet d'obtenir effectivement un automate qui s'avère de plus être minimal. (fr)
- In the theory of formal languages, the Myhill–Nerode theorem provides a necessary and sufficient condition for a language to be regular. The theorem is named for John Myhill and Anil Nerode, who proved it at the University of Chicago in 1958. (en)
- マイヒル–ネローデの定理（英: Myhill–Nerode theorem）とは、ある形式言語が正規言語であるための必要十分条件を提示した定理である。ほとんどの場合、ある言語が正規言語でないことを証明するのに使われる。 名称は1958年にこの定理を発見したシカゴ大学の John Myhill と Anil Nerode が由来である。 (ja)
- Nella teoria dei linguaggi formali il teorema di Myhill-Nerode fornisce una condizione necessaria e sufficiente per stabilire se un linguaggio sia regolare o meno. Secondo il teorema di Myhill-Nerode, ogni linguaggio regolare sull'alfabeto consiste nell'unione di classe di equivalenza di una relazione invariante a destra di indice finito sulla chiusura di Kleene di . (it)
- De stelling van Myhill-Nerode geeft een noodzakelijke en voldoende voorwaarde die aangeeft wanneer een formele taal regulier is. De stelling luidt, dat een formele taal regulier is, dan en slechts dan als haar Myhill-Nerode-equivalentie eindig veel equivalentieklassen heeft. De stelling werd genoemd naar de wiskundigen en , die haar in 1958 voor het eerst bewezen. (nl)
- Twierdzenie Myhilla-Nerode’a – twierdzenie w teorii języków formalnych podające konieczne i dostateczne warunki na to, by dany język był regularny. Zostało udowodnione w 1958 roku przez Johna Myhilla i . (pl)
- В теории формальных языков теорема Майхилла — Нероуда определяет необходимое и достаточное условия регулярности языка. Теорема названа в честь Джона Майхилла и Энила Нероуда, доказавших её в Чикагском университете в 1958 году. (ru)
- Acerca da teoria de Linguagens Formais, o Teorema de Myhill-Nerode fornece uma condição necessária e suficiente para que uma linguagem seja regular. O nome do teorema refere-se a John Myhill e , que o provaram na Universidade de Chicago em 1958. (pt)
- 在形式语言理论中，Myhill–Nerode 定理提供了一个语言是正则语言的必要和充分条件。它近乎专门的被用来证明一个给定语言不是正则的。 这个定理得名于 和 ，他们于1958年在芝加哥大学证明了这个定理。 (zh)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
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)