سلام
گرامر خطی راستو چجوری به چپ تبدیل میکنند و بلعکس؟
(۱۱ دى ۱۳۹۱ ۰۱:۲۵ ب.ظ)z522msn نوشته شده توسط: سلام
گرامر خطی راستو چجوری به چپ تبدیل میکنند و بلعکس؟
سلام .
گرامر خطی راست رو با استفاده از قضیه تبدیل کن به NFA
NFA رو با استفاده از قضیه تبدیل کن به گرامر خطی چپ
سلام
راه ساده تری نیستش? مسلا جای متغیرشو عوض کرد و ترمینال هاشو معکوس. کرد?
s-> abcA
بشه
s->Acba
(۱۱ دى ۱۳۹۱ ۰۱:۲۵ ب.ظ)z522msn نوشته شده توسط: سلام
گرامر خطی راستو چجوری به چپ تبدیل میکنند و بلعکس؟
برای تبدیل گرامرای خطی راست به چپ اول NFA گرامر اصلی رو به دست بیار ، بعد اگه این NFA چند تا حالت نهایی داشت باید تبدیلش کنی به یک حالت نهایی ، واسه این کار یک حالت جدید بکش بعد نهاییش کن و بعد از اون حالت نهایی های NFA اصلی با گذر لاندا برو به حالت جدیدت.
حالا حالت شروع رو به حالت نهایی و حالت نهایی رو به حالت شروع تبدیل کن.
بعد جهت یال های گراف رو عوض کن.
حالا گرامر خطی راست رو با استفاده از NFA جدیدی که بدست اوردی بنویس. بعدش سمت راست قواعد رو معکوس کن...
گرامرت حالا خطی چپ شده...
(۱۱ دى ۱۳۹۱ ۰۲:۰۴ ب.ظ)z522msn نوشته شده توسط: سلام
راه ساده تری نیستش? مسلا جای متغیرشو عوض کرد و ترمینال هاشو معکوس. کرد?
s-> abcA
بشه
s->Acba
و همینطور برای تبدیل گرامر چپ به راست?
(۱۱ دى ۱۳۹۱ ۰۲:۰۴ ب.ظ)z522msn نوشته شده توسط: سلام
راه ساده تری نیستش? مسلا جای متغیرشو عوض کرد و ترمینال هاشو معکوس. کرد?
s-> abcA
بشه
s->Acba
نه دیگه این که نمیشه شما الان کلا زبان گرامر رو با این کار عوض کردی .
تا جایی که من میدونم راه حل میانی واسه این کار نیست به غیر اون چیزی که بالا اشاره کردم.
سلام
پس اینکه مینویسم درسته دیگه:
اگه بخوایم گرامر خطی راستو به چپ تبدیل کنیم nfa شو بدست میاریم (منظورم nfa گرامر خطی راسته)بعد از اینکه یه حالت نهایی ساختیم < حالت نهایی رو به اولیه و بلاعکس تبدیل میکنیم و جهت یالهاشو معکوس میکنیم و اسم گرافها تغییر پیدا میکنه وگراف خطی راستشو مینویسیم و در اخر قسمت تولیدو معکوس میکنیم
.
و
اگه بخوایم گرامر خطی چپو به راست تبدیل کنیم ترمینال هاشو معکوس میکنیم ومتغیرشو در سمت راست قرار میدهیم .
درست نوشتم یا نه؟؟؟؟
والا واسه اینکه مثلا بخایم یک گرامر چپگرد رو براش NFA بکشیم فکر نمیکنم به این سادگیا بشه. (من که هر چی فکر میکنم نمیدونم تابع تحول NFA اش چطوری میشه.
ولی خیلی سادست ، واسه اینکه یک گرامر چپگرد رو راستگرد کنی باید قواعد بازگشتی چپ رو حدف و به قواعد بازگشتی راست تبدیل کنی.
شبه نرمال سازی یه گرامر...
سلام . با یک مثال روال کار رو بررسی میکنیم .
فرض کنید گرامر خطی راست زیر رو داریم
[tex]S\rightarrow aaS|bA[/tex]
[tex]A\rightarrow bbA|\lambda[/tex]
[tex]A\rightarrow bbA|\lambda[/tex]
ابتدا اونو به یک ماشین متنهای تبدیل میکنیم . تبدیل این گرامر به ماشین کار زیاد سختی نیست
[attachment=8673]
در ادامه این ماشین رو با قوانین زیر تبدیل به گرامر خطی چپ میکنیم
۱/ متغیر S گرامر همون حالت شروع ماشین است
۲/ به ازای انتقالی مثل از B به A با الفبای a یک قاعده به فرم [tex]A\rightarrow Ba[/tex] به گرامر اضافه میکنیم
۳/ به ازای انتقالی مثل از B به A با الفبای [tex]\lambda[/tex] یک قاعده به فرم [tex]A\rightarrow B[/tex] به گرامر اضافه میکنیم
۴/ اگر A یک حالت نهایی باشد قاعده [tex]A\rightarrow \lambda[/tex] رو به قواعد گرامر اضافه میکنیم
پس در نهایت گرامر خطی چپ به فرم زیر است
[tex]S\rightarrow T_{1}a[/tex]
[tex]A\rightarrow Sb|T_{2}a|\lambda[/tex]
[tex]T_{1}\rightarrow Sa[/tex]
[tex]T_{2}\rightarrow Ab[/tex]
[tex]A\rightarrow Sb|T_{2}a|\lambda[/tex]
[tex]T_{1}\rightarrow Sa[/tex]
[tex]T_{2}\rightarrow Ab[/tex]
سلام تو این سواله نمیشه t1 و t2 در نظر نگرفت تو حالت کلی nfa رو رسم کرد و به گرامر چپ تبدیلش کرد؟معکوس کنیم و ازاین چیزا؟
تو چپ به راست اینو درست نوشتم؟
" اگه بخوایم گرامر خطی چپو به راست تبدیل کنیم ترمینال هاشو معکوس میکنیم ومتغیرشو در سمت راست قرار میدهیم .
"