| dbo:abstract
|
- Kurodova normální forma je tvar formální gramatiky, ve které jsou všechna odvozovací pravidla tvaru: AB → CDA → BCA → BA → a kde A, B, C a D jsou neterminální symboly, a je terminální symbol. Někteří autoři nepřipouštějí pravidla tvaru A → B. Pro gramatiky tohoto tvaru používal a několik dalších autorů původně název lineární omezená gramatika (anglicky linear bounded grammar). (cs)
- Die Kuroda-Normalform ist ein Begriff der Theoretischen Informatik, der im Zusammenhang mit kontextsensitiven Sprachen von Interesse ist. Sie ist nach dem Linguisten benannt und beschreibt eine Normalform der monotonen Grammatiken, also eine Teilmenge der monotonen Grammatiken, die gegenüber der Menge aller monotonen Grammatiken nichts an Ausdrucksstärke einbüßt. Die Bedeutung der Kuroda-Normalform liegt in der sehr einfachen Struktur der Produktionen. Weil monotone Grammatiken und kontextsensitive Grammatiken gelegentlich nicht unterschieden werden, wird die Kuroda-Normalform auch als Normalform der kontextsensitiven Grammatiken bezeichnet. Die Kuroda-Normalform ist eine Verallgemeinerung der Chomsky-Normalform, die eine Normalform für kontextfreie Grammatiken ist. (de)
- In formal language theory, a context-sensitive grammar is in Kuroda normal form if all production rules are of the form: AB → CD orA → BC orA → B orA → a where A, B, C and D are nonterminal symbols and a is a terminal symbol. Some sources omit the A → B pattern. It is named after Sige-Yuki Kuroda, who originally called it a linear bounded grammar—a terminology that was also used by a few other authors thereafter. Every grammar in Kuroda normal form is noncontracting, and therefore, generates a context-sensitive language. Conversely, every context-sensitive language which does not generate the empty string can be generated by a grammar in Kuroda normal form. A straightforward technique attributed to György Révész transforms a grammar in Kuroda's form to Chomsky's CSG: AB → CD is replaced by four context-sensitive rules AB → AZ, AZ → WZ, WZ → WD and WD → CD. This technique also proves that every noncontracting grammar is context-sensitive. There is a similar normal form for unrestricted grammars as well, which at least some authors call "Kuroda normal form" too: AB → CD orA → BC orA → a orA → ε where ε is the empty string. Every unrestricted grammar is weakly equivalent to one using only productions of this form. If the rule AB → CD is eliminated from the above, then one obtains context-free languages. The Penttonen normal form (for unrestricted grammars) is a special case where first rule above is AB → AD. Similarly, for context-sensitive grammars, the Penttonen normal form, also called the one-sided normal form (following Penttonen's own terminology) is: AB → AD orA → BC orA → a For every context-sensitive grammar, there exists a weakly equivalent one-sided normal form. (en)
- En informatique théorique, et particulièrement en théorie des langages formels, une grammaire contextuelle est dite en forme normale de Kuroda si ses règles de production sont de l'une des formes suivantes : où et sont des symboles non terminaux et est un symbole terminal. Certains auteurs omettent dans la définition les règles de renommage de la forme . La forme normale porte le nom de Sige-Yuki Kuroda, qui appelait ces grammaires des grammaires linéaires bornées — une terminologie qui a également été utilisée par d'autres auteurs par la suite. Une grammaire sous forme normale de Kuroda est non contractante et engendre donc un langage contextuel. Inversement, tout langage contextuel qui n'engendre pas la chaîne vide peut être engendré par une grammaire en forme normale de Kuroda. Une technique simple, attribuée à György Révész, pour mettre une grammaire quadratique de Chomsky en forme de Kuroda est la suivante : une règle est remplacée par quatre règles contextuelles , , et . Cette technique donne également une preuve de ce que toute grammaire non contractante est sensible au contexte. Il existe également une forme normale similaire pour les grammaires non expansive, et que certains auteurs appellent également la « forme normale de Kuroda » . Les règles sont alors : où est la chaîne vide. Toute grammaire générale est faiblement équivalente à une grammaire utilisant uniquement des productions de cette forme. Si la règle est omise dans ce qui précède, on obtient des langages context-free. La forme normale de Penttonen (pour les grammaires générales) est le cas particulier où la première règle ci-dessus est de la forme . De même, pour les grammaires contextuelles, la forme normale de Penttonen, également appelée forme normale unilatère selon la propre terminologie de Penttonen est la suivante : Pour toute grammaire contextuelle, il existe une forme normale unilatère faiblement équivalente. (fr)
- 形式言語理論において、ある形式文法の全ての生成規則が次のいずれかの形式をもつとき、その文法は黒田標準形（くろだひょうじゅんけい Kuroda normal form）であるという： AB → CDA → BCA → BA → α ここで A, B, C, D は非終端記号であり α は終端記号である。 黒田標準形をもつ文法によって生成される言語は全て文脈依存言語である。逆に、空文字列を含まない文脈依存言語は全て黒田標準形をもつ文法によって生成することができる。 言語学者黒田成幸の研究に基づく。 (ja)
- In informatica, una grammatica formale è espressa in forma normale di Kuroda se tutte le sue produzioni sono della forma: AB → CD oppureA → BC oppureA → B oppureA → α dove A, B, C e D sono simboli non terminali α è un simbolo terminale. Ogni grammatica in forma normale di Kuroda genera un Linguaggio sensibile al contesto, e, viceversa, ogni linguaggio sensibile al contesto che non produce la stringa vuota può essere generata da una grammatica in forma normale di Kuroda. (it)
- Gramatyka formalna jest w postaci normalnej Kurody, jeśli zawiera tylko produkcje postaci: gdzie A,B i C to symbole nieterminalne, a – symbol terminalny. Każda gramatyka w postaci normalnej Kurody generuje język kontekstowy, jak również dla każdej gramatyki kontekstowej nie generującej słowa pustego istnieje równoważna jej gramatyka w postaci normalnej Kurody. (pl)
- Na linguagem formal, a gramática está na forma normal de Kuroda se todas as produções são da forma: AB → CD ou A → BC ou A → B ou A → α Onde A,B,C e D são símbolos não terminais e α um síbolo terminal. Alguns autores omitem a terceira cláusula (A → B). Foi nomeado assim em homenagem a Sige-Yuki Kuroda, o qual originalmente chamava de gramática linearmente limitada—terminologia ainda utilizada por muitos autores.Toda gramática na forma normal de Kuroda está na forma não contraída e portanto é possível gerar uma linguagem sensível ao contexto. Reciprocamente, toda linguagem sensível ao contexto, a qual não gere uma cadeia vazia, pode ser gerada por uma gramática na forma normal de Koruda. Uma técnica genuínamente atribuída a György Révész transforma a gramática na forma normal de Koruda para a forma normal de Chomsky AB → CD é substituída por quatro regras sensíveis ao contexto AB → AZ, AZ → WZ, WZ → WD e WD → CD. Esta técnica também prova que qualquer gramática na sua forma não contráida, é sensível ao contexto. Existe uma forma normal similar para gramática irrestrita, que alguns autores também a nomeia como forma normal de Kuroda. AB → CD ou A → BC ou A → a ou A → ε Onde ε é uma string vazia. Toda gramática irrestrita é (fracamente) equivalente as gramáticas utilizando apenas produções dessa forma. Se a regra AB → CD for eliminada, como no exemplo abaixo, então são obtidas linguagens livres de contexto. (pt)
- 在计算机科学中，形式文法是 Kuroda 范式的，当且仅当所有产生规则都有如下形式: AB → CD 或A → BC 或A → B 或A → α 这里的 A, B, C 和 D 是非终结符而 α 是终结符。 所有 Kuroda 范式的文法都是单调的，因此生成上下文有关语言。反过来说，所有不生成空串的上下文有关语言都可以被 Kuroda 范式的文法所生成。 (zh)
|
| rdfs:comment
|
- Kurodova normální forma je tvar formální gramatiky, ve které jsou všechna odvozovací pravidla tvaru: AB → CDA → BCA → BA → a kde A, B, C a D jsou neterminální symboly, a je terminální symbol. Někteří autoři nepřipouštějí pravidla tvaru A → B. Pro gramatiky tohoto tvaru používal a několik dalších autorů původně název lineární omezená gramatika (anglicky linear bounded grammar). (cs)
- 形式言語理論において、ある形式文法の全ての生成規則が次のいずれかの形式をもつとき、その文法は黒田標準形（くろだひょうじゅんけい Kuroda normal form）であるという： AB → CDA → BCA → BA → α ここで A, B, C, D は非終端記号であり α は終端記号である。 黒田標準形をもつ文法によって生成される言語は全て文脈依存言語である。逆に、空文字列を含まない文脈依存言語は全て黒田標準形をもつ文法によって生成することができる。 言語学者黒田成幸の研究に基づく。 (ja)
- In informatica, una grammatica formale è espressa in forma normale di Kuroda se tutte le sue produzioni sono della forma: AB → CD oppureA → BC oppureA → B oppureA → α dove A, B, C e D sono simboli non terminali α è un simbolo terminale. Ogni grammatica in forma normale di Kuroda genera un Linguaggio sensibile al contesto, e, viceversa, ogni linguaggio sensibile al contesto che non produce la stringa vuota può essere generata da una grammatica in forma normale di Kuroda. (it)
- Gramatyka formalna jest w postaci normalnej Kurody, jeśli zawiera tylko produkcje postaci: gdzie A,B i C to symbole nieterminalne, a – symbol terminalny. Każda gramatyka w postaci normalnej Kurody generuje język kontekstowy, jak również dla każdej gramatyki kontekstowej nie generującej słowa pustego istnieje równoważna jej gramatyka w postaci normalnej Kurody. (pl)
- 在计算机科学中，形式文法是 Kuroda 范式的，当且仅当所有产生规则都有如下形式: AB → CD 或A → BC 或A → B 或A → α 这里的 A, B, C 和 D 是非终结符而 α 是终结符。 所有 Kuroda 范式的文法都是单调的，因此生成上下文有关语言。反过来说，所有不生成空串的上下文有关语言都可以被 Kuroda 范式的文法所生成。 (zh)
- Die Kuroda-Normalform ist ein Begriff der Theoretischen Informatik, der im Zusammenhang mit kontextsensitiven Sprachen von Interesse ist. Sie ist nach dem Linguisten benannt und beschreibt eine Normalform der monotonen Grammatiken, also eine Teilmenge der monotonen Grammatiken, die gegenüber der Menge aller monotonen Grammatiken nichts an Ausdrucksstärke einbüßt. Die Bedeutung der Kuroda-Normalform liegt in der sehr einfachen Struktur der Produktionen. Weil monotone Grammatiken und kontextsensitive Grammatiken gelegentlich nicht unterschieden werden, wird die Kuroda-Normalform auch als Normalform der kontextsensitiven Grammatiken bezeichnet. (de)
- In formal language theory, a context-sensitive grammar is in Kuroda normal form if all production rules are of the form: AB → CD orA → BC orA → B orA → a where A, B, C and D are nonterminal symbols and a is a terminal symbol. Some sources omit the A → B pattern. It is named after Sige-Yuki Kuroda, who originally called it a linear bounded grammar—a terminology that was also used by a few other authors thereafter. There is a similar normal form for unrestricted grammars as well, which at least some authors call "Kuroda normal form" too: AB → CD orA → BC orA → a orA → ε AB → AD orA → BC orA → a (en)
- En informatique théorique, et particulièrement en théorie des langages formels, une grammaire contextuelle est dite en forme normale de Kuroda si ses règles de production sont de l'une des formes suivantes : où et sont des symboles non terminaux et est un symbole terminal. Certains auteurs omettent dans la définition les règles de renommage de la forme . La forme normale porte le nom de Sige-Yuki Kuroda, qui appelait ces grammaires des grammaires linéaires bornées — une terminologie qui a également été utilisée par d'autres auteurs par la suite. (fr)
- Na linguagem formal, a gramática está na forma normal de Kuroda se todas as produções são da forma: AB → CD ou A → BC ou A → B ou A → α Onde A,B,C e D são símbolos não terminais e α um síbolo terminal. Alguns autores omitem a terceira cláusula (A → B). Foi nomeado assim em homenagem a Sige-Yuki Kuroda, o qual originalmente chamava de gramática linearmente limitada—terminologia ainda utilizada por muitos autores.Toda gramática na forma normal de Kuroda está na forma não contraída e portanto é possível gerar uma linguagem sensível ao contexto. Reciprocamente, toda linguagem sensível ao contexto, a qual não gere uma cadeia vazia, pode ser gerada por uma gramática na forma normal de Koruda. (pt)
|
