すべての可能なDCFLを生成するのに十分なS-GRAMMARですか？

Question

S-grammarのすべてのプロダクションはA → 𝑎𝛼 , A∈V , a∈T , 𝛼∈V*

の形式です。

"...そしてPAのペア（A、A）はPで一度だけ発生します。 [p]リンツ、6番目の編、p。 144]

s文法は明白であり、（確かではない）私たちはS-Grammarによってすべての明確なCFLを表すことができると思います。私は知っています cak-grammarはすべての可能なdcflを記述していますか？この文によれば、私たちはそれをすることができないと思いますが、私はそれについてはわからない：

残念ながら、典型的なプログラミング言語のすべての機能はS文法によって表現できるわけではありません。 [p]リンツ、6番目の編、p。 152]

しかし S文法によって記述されたすべての言語は決定論的です。

この定義で単純な文法に2段階のDPDAを作ることができるので、これを言います。

R ≝ Production Rules of CFG
(x,y,"LBL") is a labeled-edge between x and y with “LBL” as a label 
∀r∊R: r= (A,aⱰ) ( A∊V ⋀ a∊T ∧ Ɒ∊V*) add (q,q,"a,A/Ɒ") to E
Add (q,q,"ε,z/Sz′") to E
Add (q,f,"ε,z′/z′") to E

.

DCFLがあれば、S文法を提供することができない場合は、間違っている場合は訂正してください。

ありがとう。

Answer 1

実際には受け入れられていない言語の例は、専門性のために非常に簡単になる可能性があります。言語 $ A ^ * $ は、S文法によって生成されません。

実際には、S-GRAMMARは $ \ varepsilon $ を生成できません。 $ s $ を削除するには、少なくとも1つの生産を適用しなければならず、任意の生産は端末シンボルを生成します。

しかし、これを専門性として見たとしても、どちらが別の文字列を生成することはできません。すべての検証が書き直されたために $ \ alpha $ を生成できる場合（スタックには新しい $ \ alpha \ beta $ をどのように生成しますか？最初は同じ計算に従わなければなりません。

これは、実際に生産するPDAが実際には空のスタック受容を備えたPDAです。スタックが空の場合（または実際には $ Z '$ のみがあります）私たちは受け入れなければなりません。空のスタック受容を備えた決定isistice PDAがプレフィックスを含まない言語のみを生成できることはよく知られています。文字列の終わりマーカーは通常救済策です。

リアルタイムプロパティ（毎ステップ毎のシンボルを読み取る）は大きな問題です。 言語 $ \ {a ^ ib ^ jc ^ i \ mid i、j \ ge 1 \} \ cup \ {a ^ ib ^ jd ^ j \ mid i、j} GE 1 \} $ 。それはDPDAによって受け入れることができます。 $ A $ のプッシュ $ b $ のプッシュ。その後、 $ c $ を読むとき、 $ b $ の $ A $ 'sと $ c $ です。それ以外の場合は、 $ d $ を読むとき、 $ d $ " $ b $ したがって、入力を読むことなくスタックシンボルのポップが必要です。リアルタイムPDAはそれをすることはできません（そしてS文法もしません）。私が知っているソースは、Autebert、Berstel、Boasson：コンテキスト無料言語とプッシュダウンオートマトンの正式な言語で。

もちろんPDAには単一の状態があります。私はチェックする必要があります。単一の状態制限も受け入れられた言語を減らすようです。