grammar - 文法は無限か有限か?

Question

S ::= N 
N ::= A B C X  |  D E F X
A ::= edith  | simone
B ::= de  |  ε 
C ::= wharton  | beauvoir
D ::= percy
E ::= bysshe  |  ε
F ::= shelley 
X ::= and S | ε

X を S に置き換え続ければ永遠に続けられそうですが、ε に置き換えると止まります。これは文法を無限にするか有限にするか?

Answer 1

「形式言語の文法」

、、すべてはGrammar、言語が有限または無限（任意の数の文字列で構成される）である可能性がある任意の言語の有限表現です。 AutomataRegular Expression

4つのタプラーオブジェクトによって定義された形式言語の文法：G（V _n、Σ、P、S）ここで

Vn-_変数ですfinite set。
Σ-finite set言語記号 です（文法的には端末と呼ばれます）。
P-finite set生産ルールです 。
S-変数セット（ _S∈Vn ）の要素である開始変数。

[回答]
つまり、G（V _n、Σ、P、S）で every element is finite that Why Grammar is called finite represent of a Language。

あなたの質問ではXプロダクションX::=とS| ε は、生成ルールが有限であっても、文法を使用して無限大の文字列を生成する方法を示す例です。

同様に、あらゆる種類のオートマトンもfinite represent of a languageです。

追加したい：

これらの4つのタプルを持つ文法は、あらゆる種類の言語を表すことができるため、文法はとして知られていconman represent form of any languageます。また、パーサーの作成にも実用的です。

理論的には、形式言語の研究は、自然が理解され、言語が分類されるように、有限形式での言語の表現に関するものです。