گرامر مستقل از متن برای
a^m b^n c^p d^q ; m+p<n+q
میخواستم ممنون!
سلام.
برای این سوال بهتر این هست که ابتدا ماشین PDA کشیده بشه و بعد ماشین رو به گرامر تبدیل کنیم.
کشیدن ماشین زیاد سخت نیست، باید تعداد bها و dها از تعداد aها و cها بیشتر باشه (منظورم جمع تعداد اونها بود).
در ضمن باید ترتیب هم رعایت بشه، راهنمایی کوچیک که بخوام بکنم این هست که هر aیی که دیدی بجاش A بزار داخل پشته،
هر bیی که دیدی و اگه بالای پشته A بود بردار اونو (پاپ کن) اگه A نبود B بزار داخل پشته. هر cیی که دیدی و اگه بالای پشته B بود اونو پاپ کن، اگه B نبود C رو داخل پشته قرار بده. هر D که دیدی اگه بالای پشته C بود اونو بردار، اگه C نبود شاید A بالای پشته باشه که باید اوونو برداری، در نهایت اگه بالای پشته یا B و یا C باشه، رشته پذیرفته میشه. در غیر اینصورت پذیرفته نیست.
ماشین رو که رسم کردی با یکسری قواعد اون رو می تونی به گرامر تبدیل کنی.
(با سپاس از جناب جویباری )
موفق باشید.
سلام. نیاز نیست. یکم دردسر داره ولی میشه نوشت.
[tex]S\to aSd|Sd|APC|ABQ[/tex]
[tex]A\to aAb|Ab|\lambda[/tex]
[tex]B\to bBc|bB|\lambda[/tex]
[tex]C\to cCd|Cd|\lambda[/tex]
[tex]P\to bPc|bP|b[/tex]
[tex]Q\to cQd|Qd|d[/tex]
[tex]A\to aAb|Ab|\lambda[/tex]
[tex]B\to bBc|bB|\lambda[/tex]
[tex]C\to cCd|Cd|\lambda[/tex]
[tex]P\to bPc|bP|b[/tex]
[tex]Q\to cQd|Qd|d[/tex]