تفاوت میان نسخه‌های «دستور زبان مستقل از متن»

←‏تعریف رسمی: اصلاح اشتباه تایپی
برچسب: ویرایش کاربر تازه‌کار
(←‏تعریف رسمی: اصلاح اشتباه تایپی)
برچسب‌ها: ویرایش با تلفن همراه ویرایش با مرورگر تلفن همراه
که
# <math>V\, </math> :یک مجموعه محدود است: هر عضو <math> v\in V</math> را یک متغیر گویند.هر متغیر نشاندهنده یک متن یا یک عبارت متفاوت در متن است.متغیر ها را در بعضی اوقات دسته نحوی نیز میگویند.هر متغیر یک زیر زبان از زبان های تعریف شده با <math>G\, </math> را تعریف میکند.
# <math>\Sigma\,</math> مجموعه محدودی از ترمینال هاستترمینال‌هاست که جدا از <math>V\,</math> محتوای واقعی جمله را تشکیل می دهند.مجموعه ترمینال ها مجموعه ای از حروف الفبا است که با گرامر <math>G\, </math> تعریف میشودمی‌شود.
# <math>R\,</math> یک رابطه محدود از <math>V\,</math> به <math>(V\cup\Sigma)^{*}</math> ، که در آن ستاره نشاندهندهنشان‌دهندهٔ عملیات [[ستاره کلین]] است.اعضای <math>R\,</math> را قاعده یا محصول گرامر گوییم.
# <math>S\,</math> را متغیر ابتدایی گوییم. و برای نمایش کل جمله(برنامه) استفاده میشودمی‌شود. و باید عضو <math>V\,</math> باشد.
=== قاعده نمادسازی ===
[[زبان‌شناسی صورت‌گرا|قاعده تولید]] در <math>R\,</math> یعنی فرموله کردن ریاضی به شکل <math>(\alpha, \beta)\in R</math>، که <math>\alpha \in V</math> و <math>\beta \in (V\cup\Sigma)^{*}</math> که [[رشته]] از متغیر هامتغیرها است.به جای نوشتن به شکل [[زوج مرتب]] ، قاعده تولید را به شکل: <math>\alpha\rightarrow\beta</math> مینوسیند.
 
همچنین <math>\beta</math> میتواندمی‌تواند رشته ایرشته‌ای خالی باشد(رشته با طول صفر) ، که در این زمان با ε نمایش میدهندمی‌دهند. شکل <math>\alpha\rightarrow\varepsilon</math> را ε-ساخت گویند.
 
=== قوانین استفاده ===
برای هر رشته <math>u, v\in (V\cup\Sigma)^{*}</math> ، که گفته میشودمی‌شود <math>u\,</math> نتیجه میدهدمی‌دهد <math>v\,</math> و به صورت روبرو نوشته میشود : <math>u\Rightarrow v\,</math> if <math>\exists (\alpha, \beta)\in R</math> with <math>\alpha \in V</math> and <math>u_{1}, u_{2}\in (V\cup\Sigma)^{*}</math> such that <math>u\,=u_{1}\alpha u_{2}</math> and <math>v\,=u_{1}\beta u_{2}</math>.
 
=== کاربرد قاعده تکراری ===
=== CFS های مناسب ===
یک گرامر مستقل از متن را مناسب میگوییم هرگاه داشته شرایط زیر را داشته باشد:
* نماد هاینمادهای دسترسی ناپذیر نداشته باشد: <math>\forall N \in V: \exists \alpha,\beta \in (V\cup\Sigma)^*: S \stackrel{*}{\Rightarrow} \alpha{N}\beta</math>.
* نمادهای عقیم(خاصیت تولید نکردن) نداشته باشد: <math>\forall N \in V: \exists w \in \Sigma^*: N \stackrel{*}{\Rightarrow} w</math>.
* ε-ساخت نداشته باشد:<math>\forall N \in V, w \in \Sigma^*: (N, w) \in R \Rightarrow w \neq</math> ε{{سخ}}.
کاربر ناشناس