In computer science, a right regular grammar is a formal grammar (N, Σ, P, S) such that all the production rules in P are of one of the following forms: A → a - where A is a non-terminal in N and a is a terminal in Σ A → aB - where A and B are in N and a is in Σ A → ε - where A is in N and ε denotes the empty string, i.e. the string of length 0.

PropertyValue
dbpprop:abstract
  • In computer science, a right regular grammar is a formal grammar (N, Σ, P, S) such that all the production rules in P are of one of the following forms: A → a - where A is a non-terminal in N and a is a terminal in Σ A → aB - where A and B are in N and a is in Σ A → ε - where A is in N and ε denotes the empty string, i.e. the string of length 0. In a left regular grammar, all rules obey the forms A → a - where A is a non-terminal in N and a is a terminal in Σ A → Ba - where A and B are in N and a is in Σ A → ε - where A is in N and ε is the empty string. An example of a right regular grammar G with N = {S, A}, Σ = {a, b, c}, P consists of the following rules S → aS S → bA A → ε A → cA and S is the start symbol. This grammar describes the same language as the regular expression a*bc*. A regular grammar is a left regular or right regular grammar. Some textbooks and articles disallow empty production rules, and assume that the empty string is not present in languages.
  • In der theoretischen Informatik werden formale Grammatiken vom Typ 3 der Chomsky-Hierarchie auch reguläre Grammatiken genannt. Die von diesen Grammatiken erzeugbaren Sprachen heißen dementsprechend reguläre Sprachen.
  • 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 <math>X \rightarrow wY</math> a <math>X \rightarrow w</math>, kde X,Y jsou neterminály a w je řetězcem terminálů. Regulární gramatiky se také nazývají pravé lineární gramatiky. Obdobně se definují i levé lineární gramatiky, které obsahují pravidla tvaru <math>X \rightarrow Yw</math> a <math>X \rightarrow w</math>, kde X,Y jsou neterminály a w je řetězcem terminálů. Lze dokázat, že pravé a levé lineární gramatiky jsou ekvivalentni. Regulární gramatika je ve standardní formě, jestliže obsahuje pouze pravidla tvaru <math>X \rightarrow aY</math> a <math>X \rightarrow \lambda</math>, 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.
  • Une grammaire régulière, rationnelle ou à états finie permet de décrire un langage régulier. Bien que les expressions rationnelles soient le modèle de définition le plus courant d'un langage régulier, en particulier dans le domaine des langages de programmation, il ne s'en trouve pas moins que, techniquement, la reconnaissance d'un mot d'un langage régulier s'effectue par la traduction d'expressions rationnelles en grammaire régulière.
  • Una grammatica regolare, è una grammatica formale generativa. Detta anche lineare destra o lineare sinistra, secondo la gerarchia di Chomsky è una grammatica di tipo-3.
  • 情報工学における右正規文法（みぎせいきぶんぽう、Right Regular Grammar）は、形式文法(N, Σ, P, S) において P に含まれる生成規則が以下のような形式になっているものである。 A → a - ここで A は N に含まれる非終端記号で、a は Σ に含まれる終端文字である。 A → aB - ここで A と B は N に含まれ、a は Σ に含まれる。 A → ε - ここで A は N に含まれる。 左正規文法（ひだりせいきぶんぽう、Left Regular Grammar）は、以下の規則に従う。 A → a - ここで A は N に含まれる非終端記号であり、a は Σ に含まれる終端文字である。 A → Ba - ここで A と B は N に含まれ、a は Σ に含まれる。 A → ε - ここで A は N に含まれる。 右正規文法 G の例を示す。G は、N = {S, A}, Σ = {a, b, c} から構成され、Pには以下の規則がある。 S → aS S → bA A → ε A → cA S は開始記号である。この文法を等価な正規表現で表すと a*bc* となる。 正規文法（せいきぶんぽう、Regular Grammar）には、これら右正規文法と左正規文法がある。 正規文法は全ての正規言語を記述することができ、そういう意味では有限オートマトンや正規表現と等価である。さらに言えば、右正規文法も左正規文法も同じ正規言語を定義することができる。 正規文法は全て文脈自由文法に含まれる。 全ての文脈自由文法は、左正規規則と右正規規則の組み合わせに容易に変換可能である。つまり、右正規文法と左正規文法を合成することで全ての文脈自由言語を表現可能である。正規文法は左正規規則か右正規規則を使用するが、同時に両者を使用することはない。そのため、より狭い範囲の言語である正規言語だけを記述できる。 正規文法に空記号（ε）を許さない場合もある。
  • 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.
  • Gramatyka regularna to gramatyka formalna generująca język regularny. Ważne ograniczenia postaci reguł: Po lewej stronie występuje zawsze dokładnie jeden symbol nieterminalny (tak samo jak w gramatykach bezkontekstowych) Po prawej stronie występuje nie więcej niż jeden symbol nieterminalny, i tylko na końcu prawej strony. Symbole terminalne mogą występować tylko na początku lewej strony. Przykłady poprawnych reguł: <math>A \rightarrow A</math> <math>A \rightarrow B</math> <math>A \rightarrow aA</math> <math>A \rightarrow aB</math> <math>A \rightarrow abcA</math> <math>A \rightarrow abcB</math> <math>A \rightarrow \epsilon</math> <math>A \rightarrow a</math> <math>A \rightarrow abc</math> Przykłady reguł niepoprawnych: <math>AB \rightarrow cD</math> (dwa symbole nieterminalne z lewej strony) <math>A \rightarrow BC</math> (dwa symbole nieterminalne z prawej strony) <math>A \rightarrow Ba</math> (symbol nieterminalny nie znajduje się na końcu prawej strony)
  • 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.
  • В информатике, регулярная грамматика — формальная грамматика типа 3 по иерархии Хомского. Регулярные грамматики определяют в точности все регулярные языки, и поэтому эквивалентны конечным автоматам и регулярным выражениям. Регулярные грамматики являются подмножеством контекстно-свободных.
  • 在计算机科学中，正规文法是产生式规则取下述形式的一种形式文法 (N, Σ, P, S) ： A -> a ，此处的 A 是 N 中的非终结符号，a 是 Σ 中的终结符号； A -> aB ，此处的 A 和 B 是 N 中的非终结符号，a 是 Σ 中的终结符号； C -> ε ，此处的 C 是 N 中的非终结符号。 下面给出一个正规文法的例子： 文法 G = (N, Σ, P, S)，其中 N = {S, A}，Σ = {a, b, c}，S 是起始符号，P 包含下述规则： S -> aS S -> bA A -> ε A -> cA 这个文法描述的语言也可以用正则表达式 a*bc* 来表达。 正规文法描述的语言构成了正规语言类，正规语言类中的语言也可以由有限状态自动机或正则表达式来表达。
dbpprop:hasPhotoCollection
rdf:type
rdfs:comment
  • In computer science, a right regular grammar is a formal grammar (N, Σ, P, S) such that all the production rules in P are of one of the following forms: A → a - where A is a non-terminal in N and a is a terminal in Σ A → aB - where A and B are in N and a is in Σ A → ε - where A is in N and ε denotes the empty string, i.e. the string of length 0.
  • In der theoretischen Informatik werden formale Grammatiken vom Typ 3 der Chomsky-Hierarchie auch reguläre Grammatiken genannt. Die von diesen Grammatiken erzeugbaren Sprachen heißen dementsprechend reguläre Sprachen.
  • 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 <math>X \rightarrow wY</math> a <math>X \rightarrow w</math>, kde X,Y jsou neterminály a w je řetězcem terminálů. Regulární gramatiky se také nazývají pravé lineární gramatiky.
  • Une grammaire régulière, rationnelle ou à états finie permet de décrire un langage régulier. Bien que les expressions rationnelles soient le modèle de définition le plus courant d'un langage régulier, en particulier dans le domaine des langages de programmation, il ne s'en trouve pas moins que, techniquement, la reconnaissance d'un mot d'un langage régulier s'effectue par la traduction d'expressions rationnelles en grammaire régulière.
  • Una grammatica regolare, è una grammatica formale generativa. Detta anche lineare destra o lineare sinistra, secondo la gerarchia di Chomsky è una grammatica di tipo-3.
  • 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.
  • Gramatyka regularna to gramatyka formalna generująca język regularny. Ważne ograniczenia postaci reguł: Po lewej stronie występuje zawsze dokładnie jeden symbol nieterminalny (tak samo jak w gramatykach bezkontekstowych) Po prawej stronie występuje nie więcej niż jeden symbol nieterminalny, i tylko na końcu prawej strony. Symbole terminalne mogą występować tylko na początku lewej strony.
  • 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.
  • В информатике, регулярная грамматика — формальная грамматика типа 3 по иерархии Хомского. Регулярные грамматики определяют в точности все регулярные языки, и поэтому эквивалентны конечным автоматам и регулярным выражениям.
rdfs:label
  • Regular grammar
  • Reguläre Grammatik
  • Regulární gramatika
  • Grammaire régulière
  • Grammatica regolare
  • 正規文法
  • Reguliere grammatica
  • Gramatyka regularna
  • Gramática regular
  • Регулярная грамматика
  • 正则文法
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of
is owl:sameAs of