حذف بازگشتی چپ

[feri_sharp]

سلام دوستان.
توی گرامر زیر بازگشتی چپ رو من چجوری حذفش کنم؟

S->Aa|b
A->Ac|Sd|لاندا

ممنون.
موفق باشید.

[pc_students355]

سلام دوستان.
توی گرامر زیر بازگشتی چپ رو من چجوری حذفش کنم؟

S->Aa|b
A->Ac|Sd|لاندا

ممنون.
موفق باشید.

S->Aa|b
A->Zd|Zc|dz|cz
Z->c|d

[feri_sharp]

سلام دوست عزیز.
خوب ما با گرامر اصلی می تونیم رشته ی ccca رو تولید کنیم اما با گرامر شما نهایتا 2 تا c می تونه پشته یک a قرار بگیره.

[اوبالیت به بو]

درود

برای قاعده S میشه:


S-> bR
R->aR|dR


اما قاعده A نمیشه. چون ترم غیربازگشتی نداره. قاعده A به دو صورت بازگشتی از چپ هست:


بازگشتی مستقیم بدلیل وجود A->Ac
بازگشتی مبهم بدلیل A->Ac|Lambda یعنی اگر Ac تولید بشه و بعد A بره به لامبدا

قاعده A ترم غیر بازگشتی ندارد پس نمی توان براش بازگشتی از چپ رو حذف کرد.