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

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

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

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

یک گرامر منظم راست (که گرامر خطی از راست نیز نامیده میشود) دستور زبان رسمی است(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»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۲ ژوئن ۲۰۱۳).