دستور زبان صوری

یک گرامر، اساساً شامل مجموعه‌ای از قوانین برای انتقال رشته‌هاست. برای تولید یک رشته در زبان، با یک رشته شامل تک نماد آغازین شروع می‌کنیم. سپس قواعد تولید در هر دستور اعمال می‌شوند تا رشته‌ای که نه شامل نماد آغازین و نه نماد طراحی شده غیرپایانی باشد، تولید شود. یک قاعده تولید روی یک رشته، با جابجا کردن یک رخداد سمت چپ قاعده تولید در رشته، با سمت راست آن قاعده، اعمال می‌شود. زبان تشکیل شده توسط گرامر شامل تمام رشته‌های مجزا که می‌توانند بدین شکل تولید شوند می‌باشد. هر دنباله مشخص از قواعد تولید در نماد آغازین، یک رشته مجزا در زبان را ایجاد می‌کند. اگر راه‌های مختلف برای تولید یک رشته وجود داشته باشد، گرامر را مبهم می‌نامیم. برای مثال، الفبای a و b، با نماد آغازین S و قواعد تولید زیر را در نظر بگیرید:

1. S → aSb
2. S → ba

با S شروع می‌کنیم و می‌توانیم یک قاعده برای اعمال روی آن انتخاب کنیم. اگر قاعدهٔ ۱ را انتخاب کنیم، رشتهٔ aSb را به‌دست می‌آوریم. سپس اگر دوباره قاعدهٔ ۱ را برگزینیم، با جایگزینی aSb به‌جای S، رشتهٔ aaSbb را به‌دست می‌آوریم. حال اگر قاعدهٔ ۲ را انتخاب کنیم، با جایگزینی ba به‌جای S، رشتهٔ aababb به‌دست می‌آید و کار به اتمام می‌رسد. می‌توانیم به نوشتن سری انتخاب‌ها با استفاده از نمادها، آن را واضح‌تر بیان کنیم:

S => aSb => aaSbb => aababb

زبان گرامر، مجموعه نامتناهی {.... ,abab | n≥۰} = {ba, abab, aababb, aaababbb} است که a، تکرار k مرتبه از a است.

نحوهٔ گرامر

در تعریف رسمی کلاسیک گرامر مولد، که برای اولین بار توسط نوآم چامسکی مطرح شد، گرامر G شامل اجزاء زیر:

• یک مجموعه متناهی از نمادهای غیرپایانی که مجموعه‌ای مجزا از رشته‌های تشکیل شده توسط G است.
• یک مجموعه متناهی Σ از نمادهای پایانی که مجموعه‌ای مجزا از N است.
• یک مجموعه متناهی P از قواعد تولید که هر قاعده به فرم * (Σ U N) * N (Σ U N) * → (Σ U N) است که * عمل ستاره کلین و U اجتماع مجموعه‌ها را مشخص می‌کند. بدین شکل هر قاعده تولید، یک رشته از نمادها را روی رشته دیگر می‌نگارد به طوری که اولین رشته، شامل تعدادی دلخواه از نمادهاست که حداقل یکی از آنها غیر پایانی می‌باشند. دومین رشته، فقط شامل رشته تهی است که می‌تواند توسط نمادهای مخصوص (اغلب ε یا Λ) نشان داده شود.
• یک نماد متمایز SɛN که نماد آغازین است و همچنین نماد جمله نیز نامیده می‌شود.

یک گرامر به طور رسمی توسط یک چهارتایی (N, Σ, P, S) نشان داده می‌شود به طوری که یک گرامر رسمی در ادبیات، اغلب سیستم بازنویسی یا ساختار عبارت گرامر نامیده می‌شود.

عملیات یک گرامر می‌تواند از نظر رابطه‌ها روی رشته‌ها تعریف شود:

مثال

وقتی نوآم چامسکی اولین بار گرامرهای مولد را در ۱۹۵۶ رسمی کرد، او آنها را در انواعی طبقه‌بندی کرد که امروزه به نام سلسله مراتب چامسکی شناخته شده هستند. تفاوت بین این انواع، روند فزاینده سخت قواعد تولید است و می‌تواند تعداد کمتری از زبانهای رسمی را بیان کند. دو نوع مهم، گرامرهای مستقل از متن (نوع ۲) و گرامرهای منظم (نوع ۳) هستند. زبان‌هایی که بتوانند توسط چنین گرامری توصیف شوند، به ترتیب زبان‌های مستقل از متن و زبان‌های منظم نام دارند. اگرچه از گرامر نامحدود (نوع ۰) که می‌تواند هر زبانی که توسط ماشین تورینگ پذیرفته می‌شود را بیان کند، بسیار کم قدرت ترند، ولی به دلیل اجرای مؤثر تجزیه کننده‌ها بر آنها، این دو نوع گرامر بیشتر استفاده می‌شوند. برای مثال، همهٔ زبان‌های منظم می‌توانند توسط یک ماشین حالات متناهی شناخته شوند و الگوریتم‌های شناخته شده‌ای برای زیرمجموعه‌های مفید از گرامرهای مستقل از متن برای تولید تجزیه‌کننده ال‌ال و تجزیه‌کننده ال‌آر برای به رسمیت شناختن زبان‌های متناظر با گرامرهای تولید شده، وجود دارند.

گرامرهای مستقل از متن

یک گرامر مستقل از متن گرامریست که سمت چپ هر قاعده تولید آن شامل یک نماد غیر پایانیست. این محدودیت بیهوده نیست، چرا که همه زبان‌ها را نمی‌توان توسط گرامرهای مستقل از متن تولید کرد، آنهایی که توسط این گرامرها تولید می‌شوند زبان‌های مستقل از متن نام دارند.

زبان {L(G) = {abc|n≥۱ که در بالا تعریف شد، یک زبان مستقل از متن نیست و این می‌تواند توسط لم تزریق برای زبان‌های مستقل از متن ثابت شود اما برای مثال زبان {ab|n≥۱} مستقل از متن است از آنجا که می‌تواند آن را توسط گرامر G₂ با {N={S و {Σ= {a,b که S نماد آغازین و قوانین تولید به صورت زیرمیباشند، تولید کرد.

1. S→aSb
2. S→ab

یک زبان مستقل از متن می‌تواند در زمان (O(n با یک الگوریتم مانند اِرلی شناخته شود. به همین دلیل، برای هر زبان مستقل از متن ماشینی می‌تواند ساخته شود که یک رشته را به عنوان ورودی بگیرد و در زمان (O(n تشخیص دهد که این رشته عضو زبان است یا خیر که n طول آن رشته می‌باشد. زبان مستقل از متن قطعی زیر مجموعه‌ای از زبان‌های مستقل از متن است که می‌تواند در زمان خطی تشخیص داده شود. الگوریتم‌های متعددی با هدف تشخیص این مجموعه از زبان‌ها یا زیر مجموعه از آنها وجود دارد.

گرامرهای منظم

در گرامرهای منظم هم سمت چپ یک نماد غیر پایانیست با این تفاوت که سمت راست هم محدودیت دارد. سمت راست ممکن است یک رشته تهی یا یک نماد پایانی یا یک نماد پایانی که با یک نماد غیر پایانی همراه است باشد.

زبان {ab|n≥۱} که در بالا تعریف شد منظم نیست اما زبان {ab|m,n≥۱} منظم است زیرا می‌تواند توسط گرامر G₃ با N = {S,A,B}, و{Σ= {a,b نماد آغازین S و قواعد تولید زیر تولید شود:

1. S→aA
2. A→aA
3. A→bA
4. B→bB
5. B→ε

همه زبان‌هایی که توسط یک گرامر مستقل از متن تولید می‌شوند می‌توانند در زمان خطی توسط ماشین حالات متناهی شناخته شوند. اگر چه در عمل گرامرهای منظم عموماً با استفاده از عبارتهای منظم توضیح داده می‌شوند، بعضی شکل‌های عبارت منظم که در عمل استفاده می‌شوند قویا زبان‌های منظم تولید نمی‌کنند و تشخیص خطی از اجرای آن اشتقاق‌ها نشان نمی‌دهند.

گرامرهای بازگشتی

یک گرامر بازگشتی، گرامری است شامل قواعد تولیدی که بازگشتی می‌باشند. برای مثال، یک گرامر برای زبان مستقل از متن، بازگشتی چپ است اگر یک نماد غیر پایانی A وجود داشته باشد که بتوان آنرا میان قواعد تولید طوری قرار داد که رشته‌ای تولید کند که در آن A، چپ‌ترین نماد است. همهٔ انواع گرامرهای سلسله مراتب چامسکی می‌توانند بازگشتی باشند.