「終端記号と非終端記号」の版間の差分

以下、単に「集合」とあるものは全て有限集合である。この理論では文法は一般に、記号列を別の記号列に置換できるものとして定義する生成規則の集合によって定義される。これらの生成規則は、文字列の生成やパースに使われる。それぞれの生成規則は、置換される記号列からなる ''ヘッド'' （左辺）と、置換する記号列からなる ''ボディ'' （右辺）を持つ。規則は、''ヘッド'' → ''ボディ'' のような形に書く。例えば、規則 z0 → z1 は、z0 を z1 で置き換えることを表す。

* ''非終端記号'' の有限集合 <math>N</math>

* <math>N</math> と [[素集合|素]] な ''終端記号''([[アルファベット (計算機科学)|アルファベット]]) の有限集合 <math>\Sigma</math>

* ''生成規則'' の有限集合 <math>P</math> 。それぞれの規則は次のような形式であをしている：

:ここで <math>{}^{*}</math> は [[クリーネ閉包|クリーネ・のスター]]演算子（つまり、0個以上の並びを意味する）、 <math>\cup</math> は和集合を表し、よって <math>(\Sigma \cup N)^{*}</math> は0個以上の記号の並びを表す。つまり、左辺は少なくとも1つの非終端記号を含む。右辺が空文字列の場合は、誤解を避けるために <math>\Lambda</math>, <math>e</math>, <math>\epsilon</math> のような記号を使うことがある。

文法は、順序付け以上かられたなる4つ組 <math><N, \Sigma, P, S></math> として、言語が形式的に定義される。<ref>{{cite book|first=Seymour|last=Ginsburg|authorlink=Seymour Ginsburg|title=Algebraic and automata theoretic properties of formal languages|publisher=North-Holland|pages=8–9|year=1975|isbn=0-7204-2506-9}}</ref><ref>{{cite book|last=Harrison|first=Michael A.|authorlink=Michael A. Harrison|title=Introduction to Formal Language Theory|year=1978|pages=13|isbn=0-201-02955-3|location=Reading, Mass.|publisher=Addison-Wesley Publishing Company}}</ref>