Local language (formal language) (original) (raw)
En informatique théorique, et notamment en théorie des langages rationnels, un langage local est un langage formel pour lequel l'appartenance d'un mot au langage peut être testée en considérant les blocs de deux lettres consécutives ou, de manière plus imagée, en faisant glisser sur le mot une « fenêtre » de largeur 2. De manière équivalente, c'est un langage rationnel qui peut être reconnu par un automate fini déterministe d'un type particulier, appelé automate local. Ces automates et langages interviennent notamment dans la construction de Glushkov. Un langage local est un langage sans étoile.
| Property | Value |
|---|---|
| dbo:abstract | En informatique théorique, et notamment en théorie des langages rationnels, un langage local est un langage formel pour lequel l'appartenance d'un mot au langage peut être testée en considérant les blocs de deux lettres consécutives ou, de manière plus imagée, en faisant glisser sur le mot une « fenêtre » de largeur 2. De manière équivalente, c'est un langage rationnel qui peut être reconnu par un automate fini déterministe d'un type particulier, appelé automate local. Ces automates et langages interviennent notamment dans la construction de Glushkov. Un langage local est un langage sans étoile. (fr) In mathematics, a local language is a formal language for which membership of a word in the language can be determined by looking at the first and last symbol and each two-symbol substring of the word. Equivalently, it is a language recognised by a local automaton, a particular kind of deterministic finite automaton. Formally, a language L over an alphabet A is defined to be local if there are subsets R and S of A and a subset F of A×A such that a word w is in L if and only if the first letter of w is in R, the last letter of w is in S and no factor of length 2 in w is in F. This corresponds to the regular expression More generally, a k-testable language L is one for which membership of a word w in L depends only on the prefix, suffix and the set of factors of w of length k; a language is locally testable if it is k-testable for some k. A local language is 2-testable. (en) В інформатиці та математичній теорії формальних мов, локальна мова (2-тестова мова) — це формальна мова, кожне слово якої задається першою й останньою буквами та множиною недопустимих підслів. Будь-якій локальній мові можна поставити у відповідність , підвид детермінованого скінченного автомату. (uk) |
| dbo:wikiPageExternalLink | https://archive.org/details/CounterFre_00_McNa |
| dbo:wikiPageID | 37723882 (xsd:integer) |
| dbo:wikiPageLength | 3117 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1103623866 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Cambridge_University_Press dbr:Deterministic_finite_automaton dbc:Combinatorics_on_words dbr:Regular_expression dbc:Semigroup_theory dbr:Formal_language dbr:Regular_language dbc:Formal_languages dbr:Kleene_star dbr:Local_automaton dbr:Strictly_alphabetic_morphism |
| dbp:date | April 2021 (en) |
| dbp:reason | How long should the prefix and suffix be? Should their length be 1 or k-1? (en) |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Explain dbt:Reflist dbt:Formal_languages_and_grammars |
| dct:subject | dbc:Combinatorics_on_words dbc:Semigroup_theory dbc:Formal_languages |
| rdf:type | yago:Abstraction100002137 yago:Communication100033020 yago:Language106282651 yago:WikicatFormalLanguages |
| rdfs:comment | En informatique théorique, et notamment en théorie des langages rationnels, un langage local est un langage formel pour lequel l'appartenance d'un mot au langage peut être testée en considérant les blocs de deux lettres consécutives ou, de manière plus imagée, en faisant glisser sur le mot une « fenêtre » de largeur 2. De manière équivalente, c'est un langage rationnel qui peut être reconnu par un automate fini déterministe d'un type particulier, appelé automate local. Ces automates et langages interviennent notamment dans la construction de Glushkov. Un langage local est un langage sans étoile. (fr) В інформатиці та математичній теорії формальних мов, локальна мова (2-тестова мова) — це формальна мова, кожне слово якої задається першою й останньою буквами та множиною недопустимих підслів. Будь-якій локальній мові можна поставити у відповідність , підвид детермінованого скінченного автомату. (uk) In mathematics, a local language is a formal language for which membership of a word in the language can be determined by looking at the first and last symbol and each two-symbol substring of the word. Equivalently, it is a language recognised by a local automaton, a particular kind of deterministic finite automaton. More generally, a k-testable language L is one for which membership of a word w in L depends only on the prefix, suffix and the set of factors of w of length k; a language is locally testable if it is k-testable for some k. A local language is 2-testable. (en) |
| rdfs:label | Langage local (fr) Local language (formal language) (en) Локальна мова (uk) |
| owl:sameAs | freebase:Local language (formal language) yago-res:Local language (formal language) wikidata:Local language (formal language) dbpedia-fr:Local language (formal language) dbpedia-uk:Local language (formal language) https://global.dbpedia.org/id/4qvHi |
| prov:wasDerivedFrom | wikipedia-en:Local_language_(formal_language)?oldid=1103623866&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Local_language_(formal_language) |
| is dbo:wikiPageRedirects of | dbr:Local_language_(formal_languages) |
| is dbo:wikiPageWikiLink of | dbr:Deterministic_finite_automaton dbr:Induction_of_regular_languages dbr:Glushkov's_construction_algorithm dbr:Local_language_(formal_languages) |
| is foaf:primaryTopic of | wikipedia-en:Local_language_(formal_language) |