دستور زبان منظم

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در علم رایانه، قواعد دستور زبان به نوعی دستور زبان رسمی اطلاق می‌شود که قواعد یک زبان را توصیف می‌کند.

قواعد محکم دستور زبان[ویرایش]

یک گرامر منظم راست (که گرامر خطی از راست نیز نامیده می‌شود) دستور زبان رسمی است (N,∑ , p, S) که تمامی قواعد مجموعۀ p به یکی از اشکال زیر در آن وجود دارند:

  1. B -> B-a نماد غیرپایانی از N است و α یک ترمینال (پایان) از ∑
  2. B -> B-aC و C جزئی از N هستند و α جزئی از ∑
  3. B -> B-ε جزئی از N است و نمایانگر مجموعه تهی می‌باشد، یعنی طول مجموعه صفر است.

در گرامر منظم چپ (که گرامر خطی از چپ نیز نامیده می‌شود) تمامی قواعد از قالب‌های زیر تبعیت می‌کنند:

  1. A -> a که A یک نماد غیرپایانی و جزئی از N است و α یک ترمینال (پایان) و جزئی از ∑
  2. A -> Ba که A و B جزئی از N هستند و α جزئی از ∑
  3. A -> ε که A جزئی از N و ε جزئی از مجموعۀ خطی تهی است.

نمونه‌ای از گرامر منظم راست G با فرمول N = {S, A}, Σ = {a, b, c}, P شامل قواعد زیر است:

S -> aS
S -> bA
A -> ε
A -> cA

و S علامت آغاز است. این دستور زبان همان زبانی را توصیف می‌کند که در عبارت a*bc* وجود دارد.

گرامر منظم راست G هرچند طولانی‌تر، اما ساده‌تر همین توصیف را برای عبارت N = {S, A, B, C}, ∑ = {a, b, c} توضیح می‌دهد که p در آن شامل قواعد زیر است:

S -> A
A -> aA
A -> B
B -> bC
C -> ε
C -> cC

هر یک از حروف بزرگ معادل عباراتی هستند که در عبارت قاعده‌مند بعدی آغاز می‌شوند. یک گرامر منظم یک گرامر منظم راست یا چپ است. بعضی از کتب و مقالات قواعد مجموعۀ تهی را رد می‌کنند و فرض را بر این می‌گیرند که مجموعۀ تهی در زبان‌ها وجود ندارد.

گرامرهای منظم تعمیم‌یافته[ویرایش]

گرامر منظم راست تعمیم‌یافته، گرامری است که از یکی از قواعد زیر تبعیت می‌کند:

  1. B -> a که B در اینجا نماد غیرقطعی و جزئی از N و α یک نماد قطعی در ∑ است.
  2. A -> wB که A و B جزئی از N و w جزئی از *∑ هستند
  3. A -> ε که A جزئی از N و ε جزئی از مجموعه تهی می‌باشد.

بعضی از نویسندگان این نوع دستور زبان را یک گرامر منظم راست (یا گرامر خطی از راست) و عبارت بالایی را یک گرامر منظم راست دقیق (یا گرامر خطی راست دقیق) می‌نامند. گرامر منظم چپ تعمیم‌یافته، دستور زبانی است که در آن تمامی قواعد از یکی از قالب‌های زیر تبعیت می‌کنند:

  1. A -> a که A یک نماد غیرقطعی و جزئی از N است و α یک نماد قطعی و جزئی از ∑
  2. A -> Bw که A و B جزئی از N هستند و w جزئی از *∑
  3. A -> ε که A جزئی از N و ε جزئی از مجموعه تهی می‌باشد.

قدرت مؤثر[ویرایش]

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

ترکیب قواعد منظم چپ و راست[ویرایش]

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

منابع[ویرایش]

مشارکت‌کنندگان ویکی‌پدیا، «Universal Turing machine»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۲ ژوئن ۲۰۱۳).