فرم نرمال چامسکی

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

در نظریه زبان صوری، یک گرامر مستقل از متن هنگامی در فرم نرمال چامسکی (نامگذاری به خاطر نوآم چامسکی) است که تمام قوانین تولید آن با فرم زیر باشید:

A \rightarrow BC یا
A \rightarrow \alpha یا
S \rightarrow \varepsilon ,

به طوریکه A, B و C کاراکترهای غیرپایانه و \alpha یک کاراکتر پایانه (کاراکتری که یک مقدار ثابت را نشان می‌دهد)، کاراکتر شروع، و S رشته تهی است. همچنین هیچ کدام از B یا C نمی‌توانند کاراکتر شروع باشند، و سومین قانون تولید فقط زمانی ظاهر می‌شود که \varepsilon در L(G)باشد، یعنی زبان توسط گرامر مستقل از متن G ایجاد شده باشد. هر گرامر در فرم نرمال چامسکی یک گرامر مستقل از متن می‌باشد و برعکس، هر گرامر مستقل از متنی را می‌توان به فرم معادل نرمال چامسکی تبدیل کرد. چندین الگوریتم برای انجام چنین تبدیلی شناخته شده است. این تبدیل در بسیاری از کتاب‌های درسی در نظریه ماشینها، مانند Hopcroft و Ullman ، ۱۹۷۹ توصیف شده است. همانطور که توسط "Lange and Leiß" اشاره شده است، اشکال این تبدیل این است که می‌تواند به بزرگ شدن نامطلوب اندازه گرامر منجر شود. اندازه یک گرامر، مجموع اندازه‌های قانون‌های تولید آن است، که در آن سایز هر قانون طول سمت راست آن به علاوه یک می‌باشد. |G| اندازه گرامر G را نشان می‌دهد، این اندازه در بدترین حالت بین |G|^2 و 2^{2 |G|} و وابسته به الگوریتم تبدیل استفاده شده، می‌باشد.

تعریف جایگزین[ویرایش]

تعریف دیگر فرم نرمال چامسکی به صورت زیر است: (برای مثال Hopcroft و Ullman، ۱۹۷۸ و Hopcroft et al. 2006)

A \rightarrow\, BC یا
A \rightarrow\, \alpha,

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

تبدیل یک گرامر به فرم نرمال چامسکی[ویرایش]

  1. معرفی S_0
    معرفی یک متغیر شروع جدید S_0 ، S_0 \rightarrow S که S متغیر شروع قبلی است.
  2. همهٔ قوانین \varepsilon را کاهش دهید.
    \varepsilon فرم‌هایی به شکل A \rightarrow \varepsilon, هستند که A \not= S_0 and A \in V, که V متغیرهای الفبای CFGهستند.
    هر قانون شامل \varepsilon در سمت راستش را حذف کنید. برای هر قانون شامل A در سمت راستش , A مجموعه‌ای از قوانین جدید از ترکیبات مختلف A است که با \varepsilon جایگزین شده یا نشده باشد.
    اگر یک قانون فقط A را به صورت تنها در سمت راست داشته باشد، قانون R = A \rightarrow \varepsilon را اضافه کنید مگر اینکه R قبلاً از پردازش حذف شده باشد.
    برای مثال گرامرG:
    S \rightarrow AbA \mid B
    B \rightarrow b \mid c
    A \rightarrow \varepsilon
    G فقط یک قانون دارد، هنگامی که A \rightarrow \varepsilon حذف شود، داریم:
    S \rightarrow AbA \mid Ab \mid bA \mid b \mid B
    B \rightarrow b \mid c
    توجه کنید که ما باید تمامی احتمالات را در نظربگیریم A \rightarrow \varepsilon و ما در واقع در نهایت ۳ قانون رااضافه می‌کنیم.
  3. همهٔ قوانین واحد را کاهش دهید
    A \rightarrow B; A,B \in V
    پس از آن که همهٔ قوانین \varepsilon حذف شدند، شما می‌توانید شروع به از بین بردن قوانین واحد، و یا قوانینی که سمت چپ آن شامل یک متغیر و هیچ ترمینالی ندارد (است که در تضاد با CNF)کنید.
    برای حذف A \rightarrow B
    \forall B \rightarrow U, که U که یک رشته از متغیرها و پایانه هاست، قانون A \rightarrow U را اضافه کنید مگر اینکه قانون پایه‌ای باشد که قبلاً حذف شده است.
  4. سایر قوانینی که در فرم نرمال چامسکی نیستند را حذف کنید
    A \rightarrow u_1 u_2 \dotso u_k, k \ge 3, u_1 \in V \cup \Sigma با A \rightarrow u_1 A_1 , A_1 \rightarrow u_2 A_2 , \dotsc , A_{k-2} \rightarrow u_{k-1} u_k, جایگذاری کنید کهA_iها متغیرهای جدید هستند.
    اگر u_i \in \Sigma, replace u_i را با متغیر V_i جایگزین کنید و قانون V_i \rightarrow u_i را اضافه کنید.

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

  • مشارکت‌کنندگان ویکی‌پدیا، «Chomsky normal form»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۱۲ بهمن ۱۳۹۲).