محتوای حذف‌شده محتوای افزوده‌شده

درخط

نسخهٔ ‏۲۰ آوریل ۲۰۱۶، ساعت ۰۷:۴۷

گرامر مستقل از متن به گرامری (G=(V،T،S،P گفته می‌شود که قانون‌های تولید آن به شکل زیر باشند: A→x که A € V و *(x € (V∪T

زبان L یک زبان مستقل از متن است اگر و تنها اگر گرامر مستقل از متنی مانند G وجود داشته باشد که رابطه ( L=L(G برقرار باشد.همه گرامرهای منظم مستقل از متن هستند؛ بنابراین یک زبان منظم مستقل از متن نیز می‌باشد اما زبان‌های نامنظمی مانند{a^n b^n}(^ توان) نیز وجود دارند که مستقل از متن باشند. هبرای این مثال یک گرامر مستقل از متن وجود دارد. بنابراین خانوادهٔ زبان‌های منظم زیر مجموعه سره‌ای از خوانده زبان‌های مستقل از متن می‌باشند. نام گرامرهای مستقل از متن از این حقیقت آمده که جانشینی متغیرهای سمت چپ قانون تولید، هرزمان که یکی از آن‌ها در یک فرم جمله‌ای ظاهر شود امکان‌پذیر است. بدین معنی که این جانشینی به دیگر نشانه‌های فرم جمله ای(متن) وابسته نیست. این ویژگی از این ناشی می‌شود که تنها یک متغیردر سمت چپ قانون‌های تولید قرار می‌گیرد.

مثال‌های از زبان‌های مستقل از متن مثال یک: گرامر (S}،{a،b}،S،P}) با قانون‌های تولید s→aSa s→bSb s→Y مستقل از متن است. نمونه‌ای از یک اشتقاق در این گرامر به صورت s→aSa→aaSaa→aabSbaa→aabbaa می‌باشد. این اشتقاق و دیگر اشتقاق‌های مشابه نشان می‌دهند که زبان {L(G)={wwR:w€{a،b یک زبان مستقل از متن است؛ اما این زبان منظم نیست. مثال دو: s→abB A→aaBb B→bbAa A→Y مستقل از متن است. زبان متناظر با این گرامر {L(G)={ab(bbaa)^nbba(ba)^n:n>=0 می‌باشد. هر دوی این مثال‌ها گرامرهایی را نشان می‌دهند که علاوه بر مستقل از متن بودن، خطی نیز هستند. گرامرهای منظم و خطی مطمئناً مستقل از متن نیز می‌باشند. اما یک گرامر مستقل از متن لزوماً خطی نیست.^[۱]

پیشینه

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

احمد، کسی که ماشین قرمزش داخل گاراژ بود ، رفت به سبزی فروشی.

می توان به طور منطقی عبارت بالا را پرانتز بندی کرد به صورت :

(احمد، ((کسی که ماشین قرمزش)((داخل گاراژ )بود)))، (رفت (به (سبزی فروشی)))).

برای توصیف متدهایی که به وسیله آن ها در برخی از زبان های طبیعی که عبارت ها از بلوک های کوچکتری ساخته شده اند ، گرامر مستقل از متن روشی ساده ودر عین حال از لحاظ ریاضی دقیق را به وسیله گرفتن ساختارهای بلوکی جملات از راه طبیعی ایجاد می کند. سادگی آن باعث می شود تا برای رسمی سازی مطالعه ریاضیات سخت جوابگو باشد . نوام چامسکی رسمی سازی گرامر مستقل از متن و همین طور کلاس بندی نوع خاصی از گرامر رسمی آن را (که وی آن را گرامرهای ساختار عبارت^[۲] نامید ) در اواسط ۱۹۵۰ به وجود آورد^[۳].چیزی که چامسکی آن را گرامر ساختار عبارت نامید به گرامر حوزه انتخاباتی مشهور است ، که به موجب آن در مقابل گرامر وابسته است.

تعریف رسمی

گرامر مستقل از متن با ۴عنصر مشخص میشود.

$G=(V\,,\Sigma \,,R\,,S\,)$ که

$V\,$ :یک مجموعه محدود است: هر عضو $v\in V$ را یک متغیر گویند.هر متغیر نشاندهنده یک متن یا یک عبارت متفاوت در متن است.متغیر ها را در بعضی اوقات دسته نحوی نیز میگویند.هر متغیر یک زیر زبان از زبان های تعریف شده با $G\,$ را تعریف میکند.
$\Sigma \,$ مجموعه محدودی از ترمینال‌هاست که جدا از $V\,$ محتوای واقعی جمله را تشکیل می دهند.مجموعه ترمینال ها مجموعه ای از حروف الفبا است که با گرامر $G\,$ تعریف می‌شود.
$R\,$ یک رابطه محدود از $V\,$ به $(V\cup \Sigma )^{*}$ ، که در آن ستاره نشان‌دهندهٔ عملیات ستاره کلین است.اعضای $R\,$ را قاعده یا محصول گرامر گوییم.
$S\,$ را متغیر ابتدایی گوییم. و برای نمایش کل جمله(برنامه) استفاده می‌شود. و باید عضو $V\,$ باشد.

قاعده نمادسازی

قاعده تولید در $R\,$ یعنی فرموله کردن ریاضی به شکل $(\alpha ,\beta )\in R$ ، که $\alpha \in V$ و $\beta \in (V\cup \Sigma )^{*}$ که رشته از متغیرها است.به جای نوشتن به شکل زوج مرتب ، قاعده تولید را به شکل: $\alpha \rightarrow \beta$ مینوسیند.

همچنین $\beta$ می‌تواند رشته‌ای خالی باشد(رشته با طول صفر) ، که در این زمان با ε نمایش می‌دهند. شکل $\alpha \rightarrow \varepsilon$ را ε-ساخت گویند.

قوانین استفاده

برای هر رشته $u,v\in (V\cup \Sigma )^{*}$ ، که گفته می‌شود $u\,$ نتیجه می‌دهد $v\,$ و به صورت روبرو نوشته میشود : $u\Rightarrow v\,$ if $\exists (\alpha ,\beta )\in R$ with $\alpha \in V$ and $u_{1},u_{2}\in (V\cup \Sigma )^{*}$ such that $u\,=u_{1}\alpha u_{2}$ and $v\,=u_{1}\beta u_{2}$ .

کاربرد قاعده تکراری

برای هر $u,v\in (V\cup \Sigma )^{*},u{\stackrel {*}{\Rightarrow }}v$ (or $u\Rightarrow \Rightarrow v\,$ in some textbooks)، اگر $\ u_{1},u_{2},\cdots u_{k}\in (V\cup \Sigma )^{*},k\geq 0$ به طوری که $u\Rightarrow u_{1}\Rightarrow u_{2}\cdots \Rightarrow u_{k}\Rightarrow v$ .

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

گرامر زبان $G=(V\,,\Sigma \,,R\,,S\,)$ بدین شکل است که :

$L(G)=\{w\in \Sigma ^{*}:S{\stackrel {*}{\Rightarrow }}w\}$

زبان $L\,$ را گرامر مستقل از متن میگویند که وجود داشته باشد $G\,$ ای ،به طوریکه $L\,=\,L(G)$ .

CFS های مناسب

یک گرامر مستقل از متن را مناسب میگوییم هرگاه داشته شرایط زیر را داشته باشد:

نمادهای دسترسی ناپذیر نداشته باشد: $\forall N\in V:\exists \alpha ,\beta \in (V\cup \Sigma )^{*}:S{\stackrel {*}{\Rightarrow }}\alpha {N}\beta$ .
نمادهای عقیم(خاصیت تولید نکردن) نداشته باشد: $\forall N\in V:\exists w\in \Sigma ^{*}:N{\stackrel {*}{\Rightarrow }}w$ .
ε-ساخت نداشته باشد: $\forall N\in V,w\in \Sigma ^{*}:(N,w)\in R\Rightarrow w\neq$ ε
.
لوپ نداشته باشد: $\neg \exists N\in V:N{\stackrel {*}{\Rightarrow }}N$ .

مثال

گرامر $G=(\{S\},\{a,b\},P,S)$ ، fh ساخت های :

S → aSa،

S → bSb،

S → ε،

یک گرامر مستقل از متن است.چون یک ε-ساخت دارد ، مناسب نیست.اشتقاق معمولی در این دستور زبان :

S → aSa → aaSaa → aabSbaa → aabbaa.

بدین شکل است.و واضح است که $L(G)=\{ww^{R}:w\in \{a,b\}^{*}\}$ .زبان مستقل از متن است حتی با اینکه زبان منظم نیست.

شکل معمولی

تمام گرامر مستقل از متن که رشته خالی تولید نمیکند را نمی توان تبدیل کردن به قانونی که رشته خالی تولید نمیکند.اگر که رشته خالی تولید میکند لازم است قانون $S\rightarrow \epsilon$ را داشته باشد ولی لازم نیست قانون ε را داشته باشد.تمام گرامر های مستقل از متن که ε-ساخت را دارند با گرامر های شکل نرمال چامسکی^[۴] و همچنین گرامر شکل نرمال گریعبچ^[۵] معادلند."معادل بودن " در اینجا به معنای آن است که هر در گرامر زبان یکسانی تولید میکند.

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

مشکلات تصمیم ناپذیر

برخی از سولات که تصمیم ناپذیرند در کلاس های وسیع تر گرامر ، در گرامر مستقل از متن تصمیم پذیر شده اند.مانند : مسئله پوچی که در گرامر وابسته به متن^[۶] تصمیم ناپذیر است ولی در گرامر مستقل از متن تصمیم پذیر است.

اما هنوز بسیاری از مسائل تصمیم ناپذیرند، مانند:

عمومیت

با توجه به CFG ، آیا زبانی از تمام رشته ها ی الفبای ترمینال استفاده شده در این قوانین را به وجود میآورد؟^[۷]^[۸]

برابری زبان

با داشتن دو CFG ،آیا آن دو یک زبان را تولید میکنند.^[۹]

گنجاندن زبان

با داشتن دو CFG ، آیا اولی تمام رشته هایی را تولید میکند که دومی تولید میکند.^[۱۰]

زمینه‌ها

یک راه برای گسترش گرامر مستقل از متن این است که اجازه دهیم غیر پایانی ها(nonterminals) که بحث میشوند، مقدار وارزش آن ها همراه با قوانین اثبات شوند.این اجازه می دهد تا ویژگی های زبان های طبیعی از قبیل توافق و مراجع، و آنالوگ به زبان های برنامه نویسی مانند استفاده درست و تعریف شناسه، در یک راه طبیعی بیان می شود.مثلا: ما یه راحتی میتوانیم بیان کنیم که فعل وفاعل در جمع و منفرد بودن باید با هم تطابق داشته باشند.در علوم کامپیوتر مثال های این گرایش در افیکس گرامر و صفت گرامر و گرامر ایندکس است .

گرامر مستقل از متن گسترش یافته آن است که در طرف راست ساختارش عبارت با قاعده بیش از گرامرهای پایان پذیر و پایانناپذیرش میتواند باشد.گرامر مستقل از متن گسترش یافته دقیقا گرامر مستقل از متن را توصیف میکند.^[۱۱]

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

برای هر زبان مستقل از متن L، یک گرامر برای ‎L-{ε}‎ وجود دارد که هر قانون تولید آن به یکی از دو صورت زیر است: A → a , A → BC ‎به یک روند تمیزکاری برای گرامر نیاز داریم که: - متغیرهای بدون استفاده را حذف کند. ‎- قوانین تولید ε را حذف کند. - قوانین تولید واحد را حدف کند.

متغیر ‎X برای گرامر ‎G=(V‎, ‎T‎, ‎P‎, ‎S)‎ مفید نامیده می‌شود اگر یک اشتقاق به صورت زیر وجود داشته باشد: S⇒αXβ⇒w که در آن: w عضو Tاستار می‌باشد. و αوβ عضو (اجتماع T,V)استار می‌باشند.

متغیر ‎X مولد نامیده می‌شود اگر‎‎: X⇒w

متغیر ‎X قابل دسترس نامیده می‌شود اگر ‎‎رشته‌های αوβ عضو (اجتماع T,V)استار‎‎ وجود داشته باشد که: S⇒αXβ

الگوریتم کشف متغیر مولد: مجموعه متغیرهای مولد را به صورت ‎‎‎g(G)‎‎ نمایش می‌دهیم.

پایه:

اگر A → w یک قانون تولید باشد، آنگاه ‎‎A‎‎‎ یک متغیر مولد است. پس خواهیم داشت: A∈g(G)‎‎

استقرا:

اگر A → α‎‎ یکی از قوانین تولید باشد و همه‌ی متغیرهای رشته‌ی α مولد باشند، ‎‎‎A‎‎ نیز مولد است.‎‎

الگوریتم کشف متغیرهای قابل دسترس:

پایه:

‎S قابل دسترس است.

استقرا:

اگر A قابل دسترس باشد و ‎‎A → α‎‎ یک قانون تولید باشد، تمام متغیرهای ‎‎α نیز قابل دسترس هستند.

قضیه:

فرض کنید ‎‎‎G‎ یک گرامر مستقل از متن باشد، گرامری که پس از انجام دو مرحله‌ی زیر به دست می‌آید، همان زبان را تعریف می‌کند و دارای متغیر بی‌استفاده نیست. 1- حذف همه‌ی متغیرهای غیرمولد و تمام قوانینی که در آنها ظاهر می‌شوند. 2- حذف همه‌ی متغیرهای غیرقابل دسترس و تمام قوانینی که در آنها ظاهر می‌شوند.

زیر شاخه ها

گرامر مستقل از متن چندین شاخه و دسته مهم دارد:

گرامر (LR(k تجزیه کردن را اجازه میدهند.اما آنها تنها میتوانند گرامر های مستقل از متن قطعی را توصیف کنند.
گرامر های LR ساده و پیش بینی LR که به ساده تر شدن تجزیه شدن کمک میکنند.
گرامر ( LL(k اجازه به تجزیه ای میدهند که ساخت آن به طور مستقیم از یک اشتقاق چپ همانطور که در بالا توضیح داده شده است باشد.
گرامر ساده که شاخه ای از شاخه گرامر(LL(1 که بیشتر به خاطر خاصیت تئوری مورد توجه قرار گرفته است.
گرامر براکتی که دارای این خاصیت است که سمبل های ترمینالی که به چپ و راست تقسیم میشوند، هر دو دارای قوانین یکسانی است.
گرامر خطی با داشتن بیش از یک غیر پایانه در سمت راست خود، بدون اینکه قانونی داشته باشد.
گرامر منظم که شاخه ای از گرامر خطی است و زبان منظم را مشخص میکند.

تجزیه LR تجزیه LL را برای حمایت از تعداد زیادی گرامر گسترش میدهند.

کاربرد زبان شناسی

نوآم چامسکی ابتدا امید داشت که بتواند محدودیت گرامر مستقل از زبان را با تغییر قوانین بهبود بخشد.^[۱۲]

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

همچنین نگاه کنید

منابع

Hopcroft, John E.; Ullman, Jeffrey D. (1979), Introduction to Automata Theory, Languages, and Computation, Addison-Wesley. Chapter 4: Context-Free Grammars، pp. 77–106; Chapter 6: Properties of Context-Free Languages، pp. 125–137.
Sipser, Michael (1997), Introduction to the Theory of Computation, PWS Publishing, ISBN 0-534-94728-X. Chapter 2: Context-Free Grammars، pp. 91–122; Section 4.1.2: Decidable problems concerning context-free languages، pp. 156–159; Section 5.1.1: Reductions via computation histories: pp. 176–183.

↑ نظریه زبان‌ها و ماشین‌ها پیتر لینز
↑ Chomsky, Noam (Sep 1956), "Three models for the description of language" (PDF), Information Theory, IEEE Transactions, 2 (3): 113–124, doi:10.1109/TIT.1956.1056813, retrieved 2007-06-18
↑ (Hopcroft و Ullman 1979), p. 106.
↑ Chomsky normal form
↑ Greibach normal form
↑ Context-sensitive grammar
↑ ^ Sipser (1997), Theorem 5.10, p. 181.
↑ ^ a b c d Hopcroft & Ullman (1979), p. 281.
↑ ^ a b c Hazewinkel, Michiel (1994), Encyclopaedia of mathematics: an updated and annotated translation of the Soviet "Mathematical Encyclopaedia", Springer, Vol. IV, p. 56, ISBN 978-1-55608-003-6.
↑ ^ a b c Hazewinkel, Michiel (1994), Encyclopaedia of mathematics: an updated and annotated translation of the Soviet "Mathematical Encyclopaedia", Springer, Vol. IV, p. 56, ISBN 978-1-55608-003-6.
↑ ^ Norvell, Theodore. "A Short Introduction to Regular Expressions and Context-Free Grammars". pp. 4. Retrieved August 24, 2012.
↑ ^ a b Chomsky, Noam (Sep 1956), "Three models for the description of language", Information Theory, IEEE Transactions 2 (3): 113–124, doi:10.1109/TIT.1956.1056813, retrieved 2007-06-18

[1] نظریه زبان‌ها و ماشین‌ها پیتر لینز

[chomsky1956-2] Chomsky, Noam (Sep 1956), "Three models for the description of language" (PDF), Information Theory, IEEE Transactions, 2 (3): 113–124, doi:10.1109/TIT.1956.1056813, retrieved 2007-06-18

[hu106-3] (Hopcroft و Ullman 1979), p. 106.

[4] Chomsky normal form

[5] Greibach normal form

[6] Context-sensitive grammar

[7] Sipser (1997), Theorem 5.10, p. 181.

[8] Hopcroft & Ullman (1979), p. 281.

[9] Hazewinkel, Michiel (1994), Encyclopaedia of mathematics: an updated and annotated translation of the Soviet "Mathematical Encyclopaedia", Springer, Vol. IV, p. 56, ISBN 978-1-55608-003-6.

[10] Hazewinkel, Michiel (1994), Encyclopaedia of mathematics: an updated and annotated translation of the Soviet "Mathematical Encyclopaedia", Springer, Vol. IV, p. 56, ISBN 978-1-55608-003-6.

[11] Norvell, Theodore. "A Short Introduction to Regular Expressions and Context-Free Grammars". pp. 4. Retrieved August 24, 2012.

[12] Chomsky, Noam (Sep 1956), "Three models for the description of language", Information Theory, IEEE Transactions 2 (3): 113–124, doi:10.1109/TIT.1956.1056813, retrieved 2007-06-18

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]

[۹]

[۱۰]

[۱۱]

[۱۲]

@@ خط ۳۰: / خط ۳۰: @@
 که
 # <math>V\, </math> :یک مجموعه محدود است: هر عضو <math> v\in V</math> را یک متغیر گویند.هر متغیر نشاندهنده یک متن یا یک عبارت متفاوت در متن است.متغیر ها را در بعضی اوقات دسته نحوی نیز میگویند.هر متغیر یک زیر زبان از زبان های تعریف شده با <math>G\, </math> را تعریف میکند.
-# <math>\Sigma\,</math> مجموعه محدودی از ترمینال هاست که جدا از <math>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>R\,</math> یک رابطه محدود از <math>V\,</math> به <math>(V\cup\Sigma)^{*}</math> ، که در آن ستاره نشان‌دهندهٔ عملیات [[ستاره کلین]] است.اعضای <math>R\,</math> را قاعده یا محصول گرامر گوییم.
-# <math>S\,</math> را متغیر ابتدایی گوییم.و برای نمایش کل جمله(برنامه) استفاده میشود.و باید عضو <math>V\,</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>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>\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>.
+برای هر رشته <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 \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> ε{{سخ}}.