| dbo:abstract
|
- En lingüística i informàtica, una gramàtica regular és una gramàtica formal en que pot ser classificada com regular-dreta o regular-esquerra. Cada gramàtica regular defineix un llenguatge regular. (ca)
- Regulární gramatika je typ formální gramatiky. Přesněji je to gramatika typu 3 podle Chomského hierarchie. Gramatika typu 3 obsahuje pravidla tvaru a , kde X,Y jsou neterminály a je řetězcem terminálů. Gramatika také může obsahovat pravidlo v případě, že se nevyskytuje na pravé straně žádného pravidla.[zdroj?!] Rozšíření regulární gramatiky o řetězce se nazývá pravá regulární gramatika. Obdobně se definují i levé regulární gramatiky, které obsahují pravidla tvaru a , kde X,Y jsou neterminály a w je řetězcem terminálů.Lze dokázat, že pravé a levé lineární gramatiky jsou ekvivalentní. Gramatika je ve standardní formě (regulární formě), jestliže obsahuje pouze pravidla tvaru a , kde X,Y jsou neterminály, a je právě jeden terminál. Jazyky generované regulárními gramatikami jsou právě jazyky rozpoznatelné konečným automatem. (cs)
- Eine reguläre Grammatik ist in der Informatik eine formale Grammatik vom Typ 3 der Chomsky-Hierarchie. Die von solchen Grammatiken erzeugten Sprachen heißen reguläre Sprachen. (de)
- En informática una gramática regular es una gramática formal (N, Σ, P, S) que puede ser clasificada como regular izquierda o regular derecha. Las gramáticas regulares sólo pueden generar a los lenguajes regulares de manera similar a los autómatas finitos y las expresiones regulares. Dos gramáticas regulares que generan el mismo lenguaje regular se denominan equivalentes. Toda gramática regular es una gramática libre de contexto. Una gramática regular derecha es aquella cuyas reglas de producción P son de la siguiente forma: 1.
* A → a, donde A es un símbolo no-terminal en N y a uno terminal en Σ 2.
* A → aB, donde A y B pertenecen a N y a pertenece a Σ 3.
* A → ε, donde A pertenece a N. Análogamente, en una gramática regular izquierda, las reglas son de la siguiente forma: 1.
* A → a, donde A es un símbolo no-terminal en N y a uno terminal en Σ 2.
* A → Ba, donde A y B pertenecen a N y a pertenece a Σ 3.
* A → ε, donde A pertenece a N. Una definición equivalente evita la regla 1 (A → a) ya que es sustituible por: A → aLL → ε en el caso de las gramáticas regulares derechas y por: A → LaL → ε en el caso de las izquierdas. Algunos autores alternativamente no permiten el uso de la regla 3 suponiendo que la cadena vacía no pertenece al lenguaje. Un ejemplo de una gramática regular G con N = {S, A}, Σ = {a, b, c}, P se define mediante las siguientes reglas: S → aSS → bAA → εA → cA donde S es el símbolo inicial. Esta gramática describe el mismo lenguaje expresado mediante la expresión regular a*bc*. Dada una gramática regular izquierda es posible convertirla, mediante un algoritmo en una derecha y viceversa. (es)
- In theoretical computer science and formal language theory, a regular grammar is a grammar that is right-regular or left-regular.While their exact definition varies from textbook to textbook, they all require that
* all production rules have at most one non-terminal symbol;
* that symbol is either always at the end or always at the start of the rule's right-hand side. Every regular grammar describes a regular language. (en)
- En informatique théorique, en théorie des langages, une grammaire régulière, rationnelle ou à états finis est une grammaire hors-contexte particulière qui décrit un langage régulier. Les grammaires régulières donnent donc une autre possibilité que les expressions rationnelles et les automates finis pour décrire un langage régulier. (fr)
- 正規文法（せいきぶんぽう、英: Regular Grammar）は、形式文法における右正規文法と左正規文法の総称。 右正規文法（みぎせいきぶんぽう、英: Right Regular Grammar）は、形式文法(N, Σ, P, S) において P に含まれる生成規則が以下のような形式になっているものである。 1.
* A → a - ここで A は N に含まれる非終端記号で、a は Σ に含まれる終端文字である。 2.
* A → aB - ここで A と B は N に含まれ、a は Σ に含まれる。 3.
* A → ε - ここで A は N に含まれる。 左正規文法（ひだりせいきぶんぽう、英: Left Regular Grammar）は、以下の規則に従う。 1.
* A → a - ここで A は N に含まれる非終端記号であり、a は Σ に含まれる終端文字である。 2.
* A → Ba - ここで A と B は N に含まれ、a は Σ に含まれる。 3.
* A → ε - ここで A は N に含まれる。 (ja)
- 정규 문법(regular grammar)은 정규 언어를 기술하는 형식 문법이다. 정규 문법은 4-튜플 에서 생성 규칙 P가 1.
* 2.
* 3.
* 으로만 구성되어 있거나(우선형 문법), 1.
* 2.
* 3.
* 으로만 구성되어 있는 것(좌선형 문법)을 말한다. 이때 , 이고 ε는 길이가 0인 문자열이다. 이 문법은 정규 언어를 완전히 표현하는 문법으로, 또한 유한 오토마타와 완전히 대응한다. 즉, 모든 정규 문법에 대응하는 유한 오토마타가 적어도 하나 있고, 반대로 모든 유한 오토마타에 대응하는 정규 문법이 적어도 하나 존재한다. 또한 이 문법은 정규식과도 대응한다. 좌선형 문법으로 만들어지는 언어는 우선형 문법으로 만들 수 있다. 반대로 우선형 문법으로 만들어지는 언어는 좌선형 문법으로 만들 수 있다. 만약 생성 규칙에서 와 꼴이 같이 존재한다면 그 문법은 정규 문법이 아니라 이라고 한다. 이 문법으로 만들어지는 언어는 정규 언어가 아닐 수도 있다. 예를 들어, 1.
* 2.
* 3.
* 는 의 문자열을 만들어내지만, 이것은 정규 언어에 속하지 않는다. (ko)
- Una grammatica regolare, in informatica, è una grammatica formale generativa. Detta anche lineare destra o lineare sinistra, secondo la gerarchia di Chomsky è una grammatica di tipo-3. (it)
- Gramatyka regularna – gramatyka formalna, za pomocą której można opisać język regularny. Istnieją dwa rodzaje gramatyk regularnych: gramatyka lewostronna, gramatyka prawostronna. Istnieje ścisły związek gramatyki lewostronnej oraz deterministycznego automatu skończonego, taki że gramatyka generuje dokładnie taki język jaki akceptuje automat. Stąd gramatyki lewostronne generują dokładnie wszystkie języki regularne. Gramatyka regularna to albo prawo albo lewostronna. (pl)
- Een reguliere grammatica is een formele grammatica (N, Σ, P, S) waarbij de productieregels aan een bepaalde vorm voldoen. Een rechts-reguliere grammatica bevat productieregels die aan de rechterkant ten hoogste 1 niet-terminaal symbool bevatten dat alleen aan het einde mag voorkomen. Analoog hieraan bevat een links-reguliere grammatica alleen productieregels met aan de rechterkant ten hoogste 1 niet-terminaal symbool dat alleen aan het begin mag voorkomen. (nl)
- Em Teoria da computação as Gramáticas regulares também conhecida como Tipo 3 da Hierarquia de Chomsky, é uma restrição sobre a forma das produções, pode-se criar uma nova classe de gramáticas de grande importância no estudo dos compiladores por possuírem propriedades adequadas para a obtenção de reconhecedores simples. Que também podem ser denominada de Expressão regular. A linguagem do tipo 3 é qualquer gramática linear. E uma gramática linear pode ser classificada em:
* Gramática linear à direita* Se todas as regras de produção são do tipo : A::= tN ou A::= t
* Gramática linear à esquerda* Se todas as regras de produção são do tipo = A::= Nt ou A::= t
* Gramática linear unitária à direita* Se todas as regras de produção são como na linear à direita e, adicionalmente |t| < 1
* Gramática linear unitária à esquerda* Se todas as regras de produção são como na linear à esquerda e, adicionalmente |t| < 1 (pt)
- Регулярна граматика — формальна граматика типу 3 за ієрархією Чомскі. Регулярні граматики визначають в точності всі регулярні мови, і тому еквівалентні кінцевим автоматам і регулярним виразами. Регулярні граматики є підмножиною контекстно-вільних. Регулярні події та вирази — це події, що можна представити у скінченних автоматах, а також відповідні вирази, складені за спеціальною алгебричною мовою (регулярна мова), яка задає ці події. (uk)
- Регулярная грамматика — формальная грамматика типа 3 по иерархии Хомского, регулярные грамматики определяют в точности все регулярные языки, и поэтому эквивалентны конечным автоматам и регулярным выражениям. Регулярные грамматики являются подмножеством контекстно-свободных. (ru)
- 在计算机科学中，正则文法是产生式规则取下述形式的一种形式文法（N, Σ, P, S）： 1.
* A -> a ，此处的A是N中的，a是Σ中的； 2.
* A -> aB，此处的A和B是N中的非终结符号，a是Σ中的终结符号； 3.
* C -> ε，此处的C是N中的非终结符号。 下面给出一个正则文法的例子：文法G = (N, Σ, P, S)，其中N = {S, A}，Σ = {a, b, c}，S是起始符号，P包含下述规则： S -> aSS -> bAA -> εA -> cA 这个文法描述的语言也可以用正则表达式a*bc* 来表达。 正则文法描述的语言构成了正则语言类，正则语言类中的语言也可以由有限状态自动机或正则表达式来表达。 (zh)
|
| rdfs:comment
|
- En lingüística i informàtica, una gramàtica regular és una gramàtica formal en que pot ser classificada com regular-dreta o regular-esquerra. Cada gramàtica regular defineix un llenguatge regular. (ca)
- Eine reguläre Grammatik ist in der Informatik eine formale Grammatik vom Typ 3 der Chomsky-Hierarchie. Die von solchen Grammatiken erzeugten Sprachen heißen reguläre Sprachen. (de)
- In theoretical computer science and formal language theory, a regular grammar is a grammar that is right-regular or left-regular.While their exact definition varies from textbook to textbook, they all require that
* all production rules have at most one non-terminal symbol;
* that symbol is either always at the end or always at the start of the rule's right-hand side. Every regular grammar describes a regular language. (en)
- En informatique théorique, en théorie des langages, une grammaire régulière, rationnelle ou à états finis est une grammaire hors-contexte particulière qui décrit un langage régulier. Les grammaires régulières donnent donc une autre possibilité que les expressions rationnelles et les automates finis pour décrire un langage régulier. (fr)
- 正規文法（せいきぶんぽう、英: Regular Grammar）は、形式文法における右正規文法と左正規文法の総称。 右正規文法（みぎせいきぶんぽう、英: Right Regular Grammar）は、形式文法(N, Σ, P, S) において P に含まれる生成規則が以下のような形式になっているものである。 1.
* A → a - ここで A は N に含まれる非終端記号で、a は Σ に含まれる終端文字である。 2.
* A → aB - ここで A と B は N に含まれ、a は Σ に含まれる。 3.
* A → ε - ここで A は N に含まれる。 左正規文法（ひだりせいきぶんぽう、英: Left Regular Grammar）は、以下の規則に従う。 1.
* A → a - ここで A は N に含まれる非終端記号であり、a は Σ に含まれる終端文字である。 2.
* A → Ba - ここで A と B は N に含まれ、a は Σ に含まれる。 3.
* A → ε - ここで A は N に含まれる。 (ja)
- 정규 문법(regular grammar)은 정규 언어를 기술하는 형식 문법이다. 정규 문법은 4-튜플 에서 생성 규칙 P가 1.
* 2.
* 3.
* 으로만 구성되어 있거나(우선형 문법), 1.
* 2.
* 3.
* 으로만 구성되어 있는 것(좌선형 문법)을 말한다. 이때 , 이고 ε는 길이가 0인 문자열이다. 이 문법은 정규 언어를 완전히 표현하는 문법으로, 또한 유한 오토마타와 완전히 대응한다. 즉, 모든 정규 문법에 대응하는 유한 오토마타가 적어도 하나 있고, 반대로 모든 유한 오토마타에 대응하는 정규 문법이 적어도 하나 존재한다. 또한 이 문법은 정규식과도 대응한다. 좌선형 문법으로 만들어지는 언어는 우선형 문법으로 만들 수 있다. 반대로 우선형 문법으로 만들어지는 언어는 좌선형 문법으로 만들 수 있다. 만약 생성 규칙에서 와 꼴이 같이 존재한다면 그 문법은 정규 문법이 아니라 이라고 한다. 이 문법으로 만들어지는 언어는 정규 언어가 아닐 수도 있다. 예를 들어, 1.
* 2.
* 3.
* 는 의 문자열을 만들어내지만, 이것은 정규 언어에 속하지 않는다. (ko)
- Una grammatica regolare, in informatica, è una grammatica formale generativa. Detta anche lineare destra o lineare sinistra, secondo la gerarchia di Chomsky è una grammatica di tipo-3. (it)
- Gramatyka regularna – gramatyka formalna, za pomocą której można opisać język regularny. Istnieją dwa rodzaje gramatyk regularnych: gramatyka lewostronna, gramatyka prawostronna. Istnieje ścisły związek gramatyki lewostronnej oraz deterministycznego automatu skończonego, taki że gramatyka generuje dokładnie taki język jaki akceptuje automat. Stąd gramatyki lewostronne generują dokładnie wszystkie języki regularne. Gramatyka regularna to albo prawo albo lewostronna. (pl)
- Een reguliere grammatica is een formele grammatica (N, Σ, P, S) waarbij de productieregels aan een bepaalde vorm voldoen. Een rechts-reguliere grammatica bevat productieregels die aan de rechterkant ten hoogste 1 niet-terminaal symbool bevatten dat alleen aan het einde mag voorkomen. Analoog hieraan bevat een links-reguliere grammatica alleen productieregels met aan de rechterkant ten hoogste 1 niet-terminaal symbool dat alleen aan het begin mag voorkomen. (nl)
- Регулярна граматика — формальна граматика типу 3 за ієрархією Чомскі. Регулярні граматики визначають в точності всі регулярні мови, і тому еквівалентні кінцевим автоматам і регулярним виразами. Регулярні граматики є підмножиною контекстно-вільних. Регулярні події та вирази — це події, що можна представити у скінченних автоматах, а також відповідні вирази, складені за спеціальною алгебричною мовою (регулярна мова), яка задає ці події. (uk)
- Регулярная грамматика — формальная грамматика типа 3 по иерархии Хомского, регулярные грамматики определяют в точности все регулярные языки, и поэтому эквивалентны конечным автоматам и регулярным выражениям. Регулярные грамматики являются подмножеством контекстно-свободных. (ru)
- 在计算机科学中，正则文法是产生式规则取下述形式的一种形式文法（N, Σ, P, S）： 1.
* A -> a ，此处的A是N中的，a是Σ中的； 2.
* A -> aB，此处的A和B是N中的非终结符号，a是Σ中的终结符号； 3.
* C -> ε，此处的C是N中的非终结符号。 下面给出一个正则文法的例子：文法G = (N, Σ, P, S)，其中N = {S, A}，Σ = {a, b, c}，S是起始符号，P包含下述规则： S -> aSS -> bAA -> εA -> cA 这个文法描述的语言也可以用正则表达式a*bc* 来表达。 正则文法描述的语言构成了正则语言类，正则语言类中的语言也可以由有限状态自动机或正则表达式来表达。 (zh)
- Regulární gramatika je typ formální gramatiky. Přesněji je to gramatika typu 3 podle Chomského hierarchie. Gramatika typu 3 obsahuje pravidla tvaru a , kde X,Y jsou neterminály a je řetězcem terminálů. Gramatika také může obsahovat pravidlo v případě, že se nevyskytuje na pravé straně žádného pravidla.[zdroj?!] Rozšíření regulární gramatiky o řetězce se nazývá pravá regulární gramatika. Obdobně se definují i levé regulární gramatiky, které obsahují pravidla tvaru a , kde X,Y jsou neterminály a w je řetězcem terminálů.Lze dokázat, že pravé a levé lineární gramatiky jsou ekvivalentní. (cs)
- En informática una gramática regular es una gramática formal (N, Σ, P, S) que puede ser clasificada como regular izquierda o regular derecha. Las gramáticas regulares sólo pueden generar a los lenguajes regulares de manera similar a los autómatas finitos y las expresiones regulares. Dos gramáticas regulares que generan el mismo lenguaje regular se denominan equivalentes. Toda gramática regular es una gramática libre de contexto. Una gramática regular derecha es aquella cuyas reglas de producción P son de la siguiente forma: A → aLL → ε en el caso de las gramáticas regulares derechas y por: (es)
- Em Teoria da computação as Gramáticas regulares também conhecida como Tipo 3 da Hierarquia de Chomsky, é uma restrição sobre a forma das produções, pode-se criar uma nova classe de gramáticas de grande importância no estudo dos compiladores por possuírem propriedades adequadas para a obtenção de reconhecedores simples. Que também podem ser denominada de Expressão regular. A linguagem do tipo 3 é qualquer gramática linear. E uma gramática linear pode ser classificada em: (pt)
|
