دستور بافت‌آزاد کیست؟ توضیح بده.
دستور بافت‌آزاد در نظریه زبان صوری، یک دستور صوری است که قواعد تولید آن را می‌توان به یک نماد غیرپایانی بدون در نظر گرفتن بافت آن اعمال کرد. از دیدگاه تخصصی، در یک دستور بافت‌آزاد، هر قاعده تولید حالت زیر را دارد:که در آن formula_2 یک نماد غیرپایانی "منفرد" است، و formula_3 یک رشته از پایانی‌ها و/یا غیرپایانی‌ها است (formula_3 می‌تواند تهی هم باشد). دستور زبان مستقل از متن به گرامری به صورت (G=(V,T،S,P گفته می‌شود که قانون‌های تولید آن به شکل زیر باشند:A→x که A € V و *(x € (V∪Tزبان L یک زبان مستقل از متن است اگر و تنها اگر گرامر مستقل از متنی مانند G وجود داشته باشد که رابطه (L=L(G برقرار باشد. همه گرامرهای منظم مستقل از متن هستند؛ بنابراین یک زبان منظم مستقل از متن نیز می‌باشد اما زبان‌های نامنظمی مانند{a^n b^n}(^ توان) نیز وجود دارند که مستقل از متن باشند. برای این مثال یک گرامر مستقل از متن وجود دارد؛ بنابراین خانوادهٔ زبان‌های منظم زیر مجموعه سره‌ای از خوانده زبان‌های مستقل از متن می‌باشند. نام گرامرهای مستقل از متن از این حقیقت آمده که جانشینی متغیرهای سمت چپ قانون تولید، هرزمان که یکی از آن‌ها در یک فرم جمله‌ای ظاهر شود امکان‌پذیر است. بدین معنی که این جانشینی به دیگر نشانه‌های فرم جمله‌ای (متن) وابسته نیست. این ویژگی از این ناشی می‌شود که تنها یک متغیر در سمت چپ قانون‌های تولید قرار می‌گیرد.مثال‌های از زبان‌های مستقل از متن مثال یک: گرامر (S},{a،b},S،P}) با قانون‌های تولید s→aSa s→bSb s→Y مستقل از متن است. نمونه‌ای از یک اشتقاق در این گرامر به صورت s→aSa→aaSaa→aabSbaa→aabbaa می‌باشد. این اشتقاق و دیگر اشتقاق‌های مشابه نشان می‌دهند که زبان {L(G)={wwR:w€{a,b یک زبان مستقل از متن است؛ اما این زبان منظم نیست. مثال دو: s→abB A→aaBb B→bbAa A→Y مستقل از متن است. زبان متناظر با این گرامر {L(G)={ab(bbaa)^nbba(ba)^n:n&gt;=۰ می‌باشد. هر دوی این مثال‌ها گرامرهایی را نشان می‌دهند که علاوه بر مستقل از متن بودن، خطی نیز هستند. گرامرهای منظم و خطی مطمئناً مستقل از متن نیز می‌باشند. اما یک گرامر مستقل از متن لزوماً خطی نیست (نظریه زبان‌ها و ماشین‌ها پیتر لینز).پیشینه.حداقل از زمان پانی، کسی که یک زبان‌شناس هندی مربوط به دوران قبل از میلاد مسیح بود، زبان شناسان گرامرهای زبان‌ها را بر اساس ساختار بلوکی آن‌ها و همین‌طور چگونگی تشکیل جملات از عبارت‌های کوچکتر و در نهایت از کلمه و حرف توصیف کرده‌اند. قسمت با اهمیت این ساختارهای بلوکی این است که هیچ وقت واحدهای منطقی با یکدیگر تداخل ندارند. برای مثال:احمد، کسی که ماشین قرمزش داخل گاراژ بود، رفت به سبزی فروشی.می‌توان به‌طور منطقی عبارت بالا را پرانتز بندی کرد به صورت:(احمد، ((کسی که ماشین قرمزش)((داخل گاراژ) بود)))، (رفت (به (سبزی فروشی)))).برای توصیف متدهایی که به وسیله آن‌ها در برخی از زبان‌های طبیعی که عبارت‌ها از بلوک‌های کوچکتری ساخته شده‌اند، گرامر مستقل از متن روشی ساده و در عین حال از لحاظ ریاضی دقیق را به وسیله گرفتن ساختارهای بلوکی جملات از راه طبیعی ایجاد می‌کند. سادگی آن باعث می‌شود تا برای رسمی‌سازی مطالعه ریاضیات سخت جوابگو باشد.نوام چامسکی رسمی‌سازی گرامر مستقل از متن و همین‌طور کلاس بندی نوع خاصی از گرامر رسمی آن را (که وی آن را گرامرهای ساختار عبارت نامید) در اواسط ۱۹۵۰ به وجود آورد. چیزی که چامسکی آن را گرامر ساختار عبارت نامید به گرامر حوزه انتخاباتی مشهور است، که به موجب آن در مقابل گرامر وابسته است.تعریف رسمی.گرامر مستقل از متن با ۴ عنصر مشخص می‌شود.formula_5کهقاعده نمادسازی.قاعده تولید در formula_12 یعنی فرموله کردن ریاضی به شکل formula_19، که formula_20 و formula_21 که رشته از متغیرها است. به جای نوشتن به شکل زوج مرتب، قاعده تولید را به شکل: formula_22 می‌نویسند.همچنین formula_23 می‌تواند رشته‌ای خالی باشد (رشته با طول صفر)، که در این زمان با ε نمایش می‌دهند. شکل formula_24 را ε-ساخت گویند.قوانین استفاده.برای هر رشته formula_25 ، که گفته می‌شود formula_26 نتیجه می‌دهد formula_27 و به صورت روبرو نوشته می‌شود : formula_28 if formula_29 with formula_20 and formula_31 such that formula_32 and formula_33.کاربرد قاعده تکراری.برای هر formula_34 (or formula_35 in some textbooks)، اگر formula_36 به‌طوری‌که formula_37.گرامر مستقل از متن.گرامر زبان formula_5 بدین شکل است که:formula_39زبان formula_40 را گرامر مستقل از متن می‌گویند که وجود داشته باشد formula_41ای، به‌طوری‌که formula_42.CFSهای مناسب.یک گرامر مستقل از متن را مناسب می‌گوییم هرگاه شرایط زیر را داشته باشد:مثال.گرامر formula_47 ، fh ساخت‌های:یک گرامر مستقل از متن است. چون یک ε-ساخت دارد، مناسب نیست. اشتقاق معمولی در این دستور زبان:بدین شکل است؛ و واضح است که formula_48. زبان مستقل از متن است حتی با اینکه زبان منظم نیست.شکل معمولی.تمام گرامر مستقل از متن که رشته خالی تولید نمی‌کند را نمی‌توان تبدیل کردن به قانونی که رشته خالی تولید نمی‌کند. اگر که رشته خالی تولید می‌کند لازم است قانون formula_49 را داشته باشد ولی لازم نیست قانون ε را داشته باشد. تمام گرامرهای مستقل از متن که ε-ساخت را دارند با گرامرهای و همچنین گرامر معادلند."معادل بودن " در اینجا به معنای آن است که در هر گرامر زبان یکسانی تولید می‌کند.به دلیل شکل به خصوص قوانین ساخت در شکل نرمال چامسکی، این شکل نرمال هم مفهوم نظری و هم عملی دارد. برای مثال، با توجه به یک گرامر مستقل از متن، می‌توان از فرم نرمال چامسکی برای ساخت چندجمله‌ای زمانی که آیا رشته داده شده در زبان توسط گرامر نشان داده شده یا خیر.مشکلات تصمیم ناپذیر.برخی از سولات که تصمیم ناپذیرند در کلاس‌های وسیع تر گرامر، در گرامر مستقل از متن تصمیم پذیر شده‌اند. مانند: مسئله پوچی که در تصمیم ناپذیر است ولی در گرامر مستقل از متن تصمیم پذیر است.اما هنوز بسیاری از مسائل تصمیم ناپذیرند، مانند:عمومیت.با توجه به CFG، آیا زبانی از تمام رشته‌ها ی الفبای ترمینال استفاده شده در این قوانین را به وجود می‌آورد؟برابری زبان.با داشتن دو CFG، آیا آن دو یک زبان را تولید می‌کنند.گنجاندن زبان.با داشتن دو CFG، آیا اولی تمام رشته‌هایی را تولید می‌کند که دومی تولید می‌کند.زمینه‌ها.یک راه برای گسترش گرامر مستقل از متن این است که اجازه دهیم غیر پایانی ها(nonterminals) که بحث می‌شوند، مقدار و ارزش آن‌ها همراه با قوانین اثبات شوند. این اجازه می‌دهد تا ویژگی‌های زبان‌های طبیعی از قبیل توافق و مراجع، و آنالوگ به زبان‌های برنامه‌نویسی مانند استفاده درست و تعریف شناسه، در یک راه طبیعی بیان می‌شود؛ مثلاً: ما یه راحتی می‌توانیم بیان کنیم که فعل وفاعل در جمع و منفرد بودن باید با هم تطابق داشته باشند. در علوم کامپیوتر مثال‌های این گرایش در افیکس گرامر و و است.گرامر مستقل از متن گسترش یافته آن است که در طرف راست ساختارش عبارت با قاعده بیش از گرامرهای پایان پذیر و پایان ناپذیرش می‌تواند باشد. گرامر مستقل از متن گسترش یافته دقیقاً گرامر مستقل از متن را توصیف می‌کند.فرم نرمال چامسکی.برای هر زبان مستقل از متن L، یک گرامر برای L-{ε} وجود دارد که هر قانون تولید آن به یکی از دو صورت زیر است:A → a , A → BCبه یک روند تمیزکاری برای گرامر نیاز داریم که:- متغیرهای بدون استفاده را حذف کند.- قوانین تولید ε را حذف کند.- قوانین تولید واحد را حذف کند.متغیر X برای گرامر G=(V, T, P, S) مفید نامیده می‌شود اگر یک اشتقاق به صورت زیر وجود داشته باشد:S⇒αXβ⇒wکه در آن:w عضو Tاستار می‌باشد؛ و αوβ عضو (اجتماع T,V)استار می‌باشند.متغیر X مولد نامیده می‌شود اگر:X⇒wمتغیر X قابل دسترس نامیده می‌شود اگر رشته‌های αوβ عضو (اجتماع T,V)استار وجود داشته باشد که:S⇒αXβالگوریتم کشف متغیر مولد:مجموعه متغیرهای مولد را به صورت g(G) نمایش می‌دهیم.اگر A → w یک قانون تولید باشد، آنگاه A یک متغیر مولد است. پس خواهیم داشت:A∈g(G)اگر A → α یکی از قوانین تولید باشد و همهٔ متغیرهای رشتهٔ α مولد باشند، A نیز مولد است.الگوریتم کشف متغیرهای قابل دسترس:S قابل دسترس است.اگر A قابل دسترس باشد و A → α یک قانون تولید باشد، تمام متغیرهای α نیز قابل دسترس هستند.فرض کنید G یک گرامر مستقل از متن باشد، گرامری که پس از انجام دو مرحلهٔ زیر به دست می‌آید، همان زبان را تعریف می‌کند و دارای متغیر بی‌استفاده نیست.زیر شاخه‌ها.گرامر مستقل از متن چندین شاخه و دسته مهم دارد:تجزیه LR تجزیه LL را برای حمایت از تعداد زیادی گرامر گسترش می‌دهند.کاربرد زبان‌شناسی.نوآم چامسکی ابتدا امید داشت که بتواند محدودیت گرامر مستقل از زبان را با تغییر قوانین بهبود بخشد.همچنین قوانین کمک دیگری برای زبان‌شناسی سنتی است. بخش عمده‌ای از دستور زایشی برای پیدا کردن راه‌های پالایش مکانیسم توصیفی عبارت ساختار دستور زبان و تحول قوانین به‌طوری‌که دقیقاً انواع چیزهایی را که توسط زبان طبیعی اجازه داده شده‌است را که می‌توان بیان کند، اختصاص داده‌است.