文脈自由言語で1または2の右側変数

Question

私は2つの質問をしており、私はそれについてもいくつか考えています。

1）各ルールの右側に1つの末端または変数を持つX-Context Free grammer（X-CFG）。

2）すべての規則の右側に2末端または可変のY-CFG。

質問：

a）は、彼らがすべての非正規言語を生成していますか？証明する。

b）すべての通常の言語を生成していますか？証明する。

回答：

A）私は、彼らは任意の非正規言語を生成傾けるよう、それは文字列のみの有限数を生成できる可能性があるため、彼らは任意の非定期的に生成することができない、X-CFGのためだと思います。

b）^^のような通常の言語は無限にあります。 CFGで無限の文字列を生成することはできません。したがって、すべての通常の言語を生成することはできません。

私は正しいですか？

私は質問についてよく分かりません。

Answer 1

はY-CFGを考えてみましょう：

 
S → aA 
S → ab 
A → Sb 

これはあなたの制約を満たすと非正規言語を生成し、そのY-CFGではないですか？ ^nは B ^Nように、N> = 1

それは述べとしてもthisを参照してください。

すべての正規文法は文脈自由で、すべてではないが、文脈自由文法は規則的です。それを理解するための例を挙げて、少し説明します。

質問を正しく理解すれば、両方の回答が間違っていると思います。

UPDATE

すべての正規文法は文脈自由です。

 
S → SS 
S → t 
S → N 
S → tN 
S → Nt 

そこで我々は終了するもの、複数の開始文字列から育つもの、物事を定義することができます：それでは質問ですが、私たちはすべてのCFGの使用して2つの変数は、（tは端子であり、Nは非末端である）を定義することができます正面に成長するものと背中に成長するもの。 CFGのすべてのケースです。だから私はあなたがすべての通常の言語を生成することができると言うでしょう。