با سلام خدمت دوستان.
برای زبان زیر یک گرامر نوع یک یا حسـاس به متـن طراحی کنید:
[tex]{0^n1^n0^n1^n|n>=0}[/tex]
سلام. اول اینکه گرامر حساس به متن نال رو نمیتونه قبول کنه. پس زبان گرامر اجتماعش با نال میشه زبانی که نوشتید.
[tex]S\to 0101|0A101[/tex]
[tex]A\to 01B[/tex]
[tex]B1\to 1B[/tex]
[tex]B0\to 0C[/tex]
[tex]C0\to 0C[/tex]
[tex]C1\to 011|D011[/tex]
[tex]0D\to D0[/tex]
[tex]1D\to E1[/tex]
[tex]1E\to E1[/tex]
[tex]0E\to 0A[/tex]
توی این گرامر عملاً یک هد داریم که به چپ و راست میره و توی هر مرور یک حرف اضافه میکنه.
پیاده سازی این گرامر برای ماشین راحت تره. گرامری که خودم استفاده میکنم گرامر پایینیه. از نظر سادگی نوشتن راحت تره:
[tex]S\to 0101|01A01[/tex]
[tex]A\to PAQ|PQ[/tex]
[tex]1P\to P1[/tex]
[tex]0P\to 001[/tex]
[tex]Q0\to 0Q[/tex]
[tex]Q1\to 011[/tex]
توی این گرامر A توی هر تکرارش یه P و یه Q ایجاد میکنه. P به سمت چپ میره و یه ۰۱ اضافه میکنه و Q هم به سمت راست میره و یه ۰۱ اضافه میکنه.