| dbo:abstract
|
- Greibachové normální forma (GNF) je tvar formální gramatiky, ve které mají všechny odvozující pravidla tvar: nebo kde A je neterminál, α je terminál, S je výchozí neterminální symbol, X je (případně prázdná) posloupnost neterminálních symbolů (ve které se nevyskytuje S, pokud gramatika obsahuje pravidlo ) a ɛ je prázdný řetězec. Gramatika v Greibachové normální formě postrádá levou rekurzi. Každá bezkontextová gramatika může být transformována do Greibachové normální formy. Forma je pojmenovaná podle její autorky . (cs)
- Die Greibach-Normalform ist ein Begriff der theoretischen Informatik, der im Zusammenhang mit kontextfreien Sprachen von Interesse ist. Sie ist nach der US-Informatikerin Sheila A. Greibach benannt und beschreibt eine Normalform der kontextfreien Grammatiken. Jede kontextfreie Grammatik, nach der nicht das leere Wort abgeleitet werden kann, kann in eine Greibach-Normalform transformiert werden. Die herausragende Eigenschaft der Greibach-Normalform ist, dass bei jedem Ableitungsschritt jeweils genau ein Terminalzeichen entsteht. Damit ist sie der natürliche Zwischenschritt bei der Umformung einer kontextfreien Grammatik in einen äquivalenten nichtdeterministischen Kellerautomaten ohne -Übergänge. Eine weitere Normalform für kontextfreie Grammatiken ist die Chomsky-Normalform. (de)
- In formal language theory, a context-free grammar is in Greibach normal form (GNF) if the right-hand sides of all production rules start with a terminal symbol, optionally followed by some variables. A non-strict form allows one exception to this format restriction for allowing the empty word (epsilon, ε) to be a member of the described language. The normal form was established by Sheila Greibach and it bears her name. More precisely, a context-free grammar is in Greibach normal form, if all production rules are of the form: where is a nonterminal symbol, is a terminal symbol, is a (possibly empty) sequence of nonterminal symbols not including the start symbol and is the start symbol. Observe that the grammar does not have left recursions. Every context-free grammar can be transformed into an equivalent grammar in Greibach normal form. Various constructions exist. Some do not permit the second form of rule and cannot transform context-free grammars that can generate the empty word. For one such construction the size of the constructed grammar is O(n4) in the general case and O(n3) if no derivation of the original grammar consists of a single nonterminal symbol, where n is the size of the original grammar. This conversion can be used to prove that every context-free language can be accepted by a real-time (non-deterministic) pushdown automaton, i.e., the automaton reads a letter from its input every step. Given a grammar in GNF and a derivable string in the grammar with length n, any top-down parser will halt at depth n. (en)
- Una gramática independiente del contexto (GIC) está en Forma normal de Greibach (FNG) si todas y cada una de sus reglas de producción tienen un consecuente que empieza por un carácter del alfabeto, también llamado símbolo terminal. Formalmente, cualquiera de las reglas tendrá la estructura:
* Donde "A" es el antecedente de la regla, que en el caso de las GIC debe ser necesariamente un solo símbolo auxiliar. Por su parte, "a" es el mencionado comienzo del consecuente y, por tanto, un símbolo terminal. Finalmente, "w" representa una concatenación genérica de elementos gramaticales, esto es, una sucesión exclusivamente de auxiliares, inclusive, pudiera ser la palabra vacía; en este caso particular, se tendría una regla llamada "terminal":
* Existe un teorema que prueba que cualquier GIC, cuyo lenguaje no contiene a la palabra vacía, si no lo está ya, se puede transformar en otra equivalente que sí esté en FNG. Para su demostración, normalmente, se procede por construcción, es decir, se plantea directamente un algoritmo capaz de obtener la FNG a partir de una GIC dada. (es)
- En informatique théorique, et notamment en théorie des langages formels, une grammaire algébrique est en forme normale de Greibach (en anglais, Greibach normal form ou GNF) si les membres droits de ses règles commencent tous par un symbole terminal, suivi éventuellement d'une ou plusieurs variables. Une variante permet une règle additionnelle pour engendrer le mot vide s'il fait partie du langage. Cette forme normale porte le nom de Sheila Greibach qui l'a introduite et a prouvé son existence. D'autres formes normales de grammaire existent, comme la forme normale de Chomsky, ou les grammaires sans récursivité gauche. La forme normale de Greibach est la plus élaborée de ces formes normales, et elle a été raffinée par la suite. (fr)
- De Greibach normaalvorm is een begrip uit de theoretische informatica, dat in het verband van contextvrije talen van belang is. Zij is vernoemd naar de informatica uit de Verenigde Staten en beschrijft een normaalvorm van een contextvrije grammatica, dus een deelverzameling van de contextvrije grammatica's die niet minder uitdrukkingskracht heeft dan de verzameling van algemene contextvrije grammatica's. De opvallendste eigenschap van de Greibach normaalvorm is, dat bij elke productieregel precies één terminaal symbool voorkomt. Daarmee is zij de natuurlijke tussenstap bij de omzetting van een contextvrije grammatica naar een equivalente niet-deterministische pushdown automaat (PDA) zonder -producties. Een ander normaalvorm voor contextvrije grammatica's is de Chomsky-normaalvorm. (nl)
- In informatica e nella teoria dei linguaggi formali, una grammatica libera dal contesto è nella Forma normale di Greibach se la parte destra di tutte le produzioni inizia con un simbolo terminale, eventualmente seguito da alcune variabili. Unica eccezione ammessa è la presenza della stringa vuota (epsilon, ε) come appartenente al linguaggio descritto. La forma normale prende il suo nome da . Più precisamente, una grammatica context-free è nella forma normale di Greibach, se tutte le regole di produzione sono nella forma: oppure dove A è un simbolo nonterminale, α è un simbolo terminale, è una sequenza di simboli nonterminali (eventualmente vuota) che non include come simbolo iniziale l'assioma, S è l'assioma, e ε è la stringa vuota. Si noti che la grammatica non presenta . Ogni grammatica context-free può essere trasformata in una grammatica equivalente posta in forma normale di Greibach. (Alcune definizioni non ammettono la definizione della seconda regola, nel qual caso una grammatica context-free che genera la stringa nulla non può essere trasformata.) In particolare, esiste una costruzione che assicura che la forma normale della grammatica risultante è nell'ordine di al più O(n4), dove n è la dimensione della grammatica originale. Tale conversione può essere usata per provare che ogni linguaggio context-free può essere accettato da un automa non-deterministico di tipo automa a pila. Data una grammatica in GNF e una stringa di lunghezza n derivabile dalla grammatica , ogni si fermerà a profondità n. (it)
- 言語の理論（形式言語の理論）において、文脈自由言語の全ての生成規則が次のように書けるとき、グライバッハ標準形(Greibach normal form)であるという。 または ここではAは非終端記号、αは終端記号、Xは開始記号以外の非終端記号からなる文字列(空を含む)をあらわし、Sは開始記号、εは空をあらわす。 また、左再帰が許されないという点において特徴的である。 全ての文脈自由文法は等価なグライバッハ標準形の文法に書換えることができる(定義によっては 2番目のεへの規則を含まないこともあるが、この場合は空列を受理しない)。これは、任意の文脈自由言語が非決定性プッシュダウンオートマトンで受理できることの証明である。 グライバッハ標準形で与えられた文法とその文法によって導出できる長さ n の文字列が与えられたとき、この文法に基づいた与えられた文字列の下向き構文解析は深さ n までに終了する。 グライバッハ標準形の名前はにちなんで名付けられたものである。 (ja)
- Postać normalna Greibach to postać gramatyki bezkontekstowej, w której wszystkie reguły są postaci: gdzie to dowolny symbol terminalny, to (być może pusty) ciąg symboli nieterminalnych. Specjalny przypadek produkcji gramatyki typu 1 i wyżej stanowi produkcja generująca wyraz pusty. Produkcja ta nie jest objęta formalną definicją gramatyki bezkontekstowej, która stwierdza, że prawa strona dowolnej produkcji nie może być krótsza niż lewa strona (monotoniczność), a co w tym konkretnym aspekcie ma miejsce. Produkcja ta jest dopuszczalna pod warunkiem, że symbol startowy nie występuje po prawej stronie żadnej produkcji danej gramatyki. W postaci normalnej Chomsky’ego, która stanowi podstawę dla postaci normalnej Greibach, produkcja ta zostaje przejęta bez zmian, ponieważ, wychodząc z założenia, że gramatyka nie zawiera symbolu startowego po prawej stronie, produkcja ta nie może zostać użyta w żadnej innej konfiguracji. Nazwa wywodzi się od Sheili Greibach. W pierwotnym zamyśle w artykule definiującym tę postać normalną z roku 1965 autorka pisze: Bezkontekstowy generator słów jest w postaci normalnej wtedy i tylko wtedy, gdy jego reguły są w postaci gdzie i są symbolami pośrednimi, a jest symbolem końcowym, tak aby jeden symbol wejściowy był przetwarzany w każdym kroku... skąd wynika, że ten specjalny przypadek produkcji nie jest zawarty w postaci. Niektóre definicje postaci obejmują jednak również i tę produkcję. Każdą gramatykę bezkontekstową można przedstawić w postaci normalnej Greibach. (pl)
- Uma gramática livre de contexto está na forma normal de quando todas as suas produções são da forma: A → aα onde A é uma variável, a é um terminal e α é uma palavra de variáveis. (pt)
- 在计算机科学中，声称一个上下文无关文法是Greibach 标准式（范式）(GNF)的意味着所有的产生规则都有如下形式： 或 这里的 A 是非终结符，α 是终结符，X 是不包括开始符号的非终结符的（可能为空）的序列，S 是开始符号，而 ε 是空串。 可观察出这种文法没有左递归。 所有上下文无关文法口可以被转换成等价的 Greibach 范式的文法。（某些定义不认可第二种形式的规则，在这种情况下能生成空串的上下文无关文法不能被如此转换。）这可以被用来证明所有上下文无关语言可以被非确定下推自动机所接受。 给定 GNF 的一个文法和长度为 n 的符合这个文法的一个可导出的字符串，任何将在深度 n 停机。 Greibach 范式得名于 。 (zh)
|
| rdfs:comment
|
- Greibachové normální forma (GNF) je tvar formální gramatiky, ve které mají všechny odvozující pravidla tvar: nebo kde A je neterminál, α je terminál, S je výchozí neterminální symbol, X je (případně prázdná) posloupnost neterminálních symbolů (ve které se nevyskytuje S, pokud gramatika obsahuje pravidlo ) a ɛ je prázdný řetězec. Gramatika v Greibachové normální formě postrádá levou rekurzi. Každá bezkontextová gramatika může být transformována do Greibachové normální formy. Forma je pojmenovaná podle její autorky . (cs)
- 言語の理論（形式言語の理論）において、文脈自由言語の全ての生成規則が次のように書けるとき、グライバッハ標準形(Greibach normal form)であるという。 または ここではAは非終端記号、αは終端記号、Xは開始記号以外の非終端記号からなる文字列(空を含む)をあらわし、Sは開始記号、εは空をあらわす。 また、左再帰が許されないという点において特徴的である。 全ての文脈自由文法は等価なグライバッハ標準形の文法に書換えることができる(定義によっては 2番目のεへの規則を含まないこともあるが、この場合は空列を受理しない)。これは、任意の文脈自由言語が非決定性プッシュダウンオートマトンで受理できることの証明である。 グライバッハ標準形で与えられた文法とその文法によって導出できる長さ n の文字列が与えられたとき、この文法に基づいた与えられた文字列の下向き構文解析は深さ n までに終了する。 グライバッハ標準形の名前はにちなんで名付けられたものである。 (ja)
- Uma gramática livre de contexto está na forma normal de quando todas as suas produções são da forma: A → aα onde A é uma variável, a é um terminal e α é uma palavra de variáveis. (pt)
- 在计算机科学中，声称一个上下文无关文法是Greibach 标准式（范式）(GNF)的意味着所有的产生规则都有如下形式： 或 这里的 A 是非终结符，α 是终结符，X 是不包括开始符号的非终结符的（可能为空）的序列，S 是开始符号，而 ε 是空串。 可观察出这种文法没有左递归。 所有上下文无关文法口可以被转换成等价的 Greibach 范式的文法。（某些定义不认可第二种形式的规则，在这种情况下能生成空串的上下文无关文法不能被如此转换。）这可以被用来证明所有上下文无关语言可以被非确定下推自动机所接受。 给定 GNF 的一个文法和长度为 n 的符合这个文法的一个可导出的字符串，任何将在深度 n 停机。 Greibach 范式得名于 。 (zh)
- Die Greibach-Normalform ist ein Begriff der theoretischen Informatik, der im Zusammenhang mit kontextfreien Sprachen von Interesse ist. Sie ist nach der US-Informatikerin Sheila A. Greibach benannt und beschreibt eine Normalform der kontextfreien Grammatiken. Jede kontextfreie Grammatik, nach der nicht das leere Wort abgeleitet werden kann, kann in eine Greibach-Normalform transformiert werden. Die herausragende Eigenschaft der Greibach-Normalform ist, dass bei jedem Ableitungsschritt jeweils genau ein Terminalzeichen entsteht. Damit ist sie der natürliche Zwischenschritt bei der Umformung einer kontextfreien Grammatik in einen äquivalenten nichtdeterministischen Kellerautomaten ohne -Übergänge. (de)
- Una gramática independiente del contexto (GIC) está en Forma normal de Greibach (FNG) si todas y cada una de sus reglas de producción tienen un consecuente que empieza por un carácter del alfabeto, también llamado símbolo terminal. Formalmente, cualquiera de las reglas tendrá la estructura:
*
* (es)
- In formal language theory, a context-free grammar is in Greibach normal form (GNF) if the right-hand sides of all production rules start with a terminal symbol, optionally followed by some variables. A non-strict form allows one exception to this format restriction for allowing the empty word (epsilon, ε) to be a member of the described language. The normal form was established by Sheila Greibach and it bears her name. More precisely, a context-free grammar is in Greibach normal form, if all production rules are of the form: Observe that the grammar does not have left recursions. (en)
- En informatique théorique, et notamment en théorie des langages formels, une grammaire algébrique est en forme normale de Greibach (en anglais, Greibach normal form ou GNF) si les membres droits de ses règles commencent tous par un symbole terminal, suivi éventuellement d'une ou plusieurs variables. Une variante permet une règle additionnelle pour engendrer le mot vide s'il fait partie du langage. Cette forme normale porte le nom de Sheila Greibach qui l'a introduite et a prouvé son existence. (fr)
- In informatica e nella teoria dei linguaggi formali, una grammatica libera dal contesto è nella Forma normale di Greibach se la parte destra di tutte le produzioni inizia con un simbolo terminale, eventualmente seguito da alcune variabili. Unica eccezione ammessa è la presenza della stringa vuota (epsilon, ε) come appartenente al linguaggio descritto. La forma normale prende il suo nome da . Più precisamente, una grammatica context-free è nella forma normale di Greibach, se tutte le regole di produzione sono nella forma: oppure Si noti che la grammatica non presenta . (it)
- De Greibach normaalvorm is een begrip uit de theoretische informatica, dat in het verband van contextvrije talen van belang is. Zij is vernoemd naar de informatica uit de Verenigde Staten en beschrijft een normaalvorm van een contextvrije grammatica, dus een deelverzameling van de contextvrije grammatica's die niet minder uitdrukkingskracht heeft dan de verzameling van algemene contextvrije grammatica's. De opvallendste eigenschap van de Greibach normaalvorm is, dat bij elke productieregel precies één terminaal symbool voorkomt. Daarmee is zij de natuurlijke tussenstap bij de omzetting van een contextvrije grammatica naar een equivalente niet-deterministische pushdown automaat (PDA) zonder -producties. (nl)
- Postać normalna Greibach to postać gramatyki bezkontekstowej, w której wszystkie reguły są postaci: gdzie to dowolny symbol terminalny, to (być może pusty) ciąg symboli nieterminalnych. Specjalny przypadek produkcji gramatyki typu 1 i wyżej stanowi produkcja Nazwa wywodzi się od Sheili Greibach. W pierwotnym zamyśle w artykule definiującym tę postać normalną z roku 1965 autorka pisze: skąd wynika, że ten specjalny przypadek produkcji nie jest zawarty w postaci. Niektóre definicje postaci obejmują jednak również i tę produkcję. (pl)
|
