زبان حساس‌به‌متن

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

ویژگی های محاسباتی ویرایش

در محاسبات، یک زبان حساس به متن که معادل با ماشین تورینگ غیر قطعی کراندار خطی می‌باشد ، آتاماتای خطی کران دار نیز نامیده می‌شود. این ماشین تورینگ غیرقطعی، یک نوار با kn خانه دارد، در آن n تعداد ورودی‌ها و k ثابتی در ارتباط با ماشین می‌باشد . این بدین معنی است که هر زبان صوری که می‌تواند توسط این ماشین تعریف شود، یک زبان حساس به متن است، و هر زبان حساس به متن توسط این ماشین تعریف می‌شود.

این مجموعه از زبان‌ها نیز به عنوان NLINSPACE یا ((NSPACE(O(n شناخته شده اند، چرا که آن‌ها می توانند با استفاده از فضای خطی بر روی یک ماشین تورینگ غیرقطعی پذیرفته شوند.^[۱] دستهٔ LINSPACE (یا ((DSPACE(O(n) به جز زمانی که از ماشین تورینگ قطعی استفاده می‌کنند، مانند هم تعریف می‌شود. واضح است که LINSPACE یک زیر مجموعه از NLINSPACE می‌باشد ، اما اینکه ایا LINSPACE=NLINSPACE باشد، مشخص نیست.^[۲]

مثال ها ویرایش

یکی از ساده‌ترین زبان‌های حساس به متن، اما نه مستقل از متن $L=\{a^{n}b^{n}c^{n}:n\geq 1\}$ : است. زبان تمام رشته‌های متشکل از n وقوع نماد "a" و سپس n تا "b" و سپس n تا "c" می‌باشد . (abc, aabbcc, aaabbbccc و ... ) یک مجموعهٔ بالایی ازین زبان، زبان باخ (Bach) ^[۳] نامیده می‌شود و به عنوان مجموعه ای از تمام رشته‌های توصیف شده‌است که در آن "b", "a" و "c" (و یا هر مجموعه ای دیگر با سه کاراکتر) اغلب به یه اندازه رخ می دهند.(aabccb, baabcaccs و ...) و همچنین حساس به متن هستند.^[۴]^[۵]

مثال دیگری از یک زبان حساس به متن است که مستقل از متن نیست. {L={a^p که در این زبان P عدد اول است. L را می‌توان به عنوان یک زبان حساس به متن نشان داد که توسط یک آتاماتای خطی کران دار ساخته شده پذیرفته می‌شود. می توان به سادگی و با استفاده از لم تزریق مربوطه برای هر یک از دسته‌های زبان نشان داد که L نه زبان منظم است و نه زبان مستقل از متن.

یک مثال از زبان بازگشتی که حساس به متن نمی‌باشد این است که هر زبان بازگشتی که جز مسائل EXPSPACE -hard باشد، مجموعه ای از جفت‌های عبارات منظم با توان می گویند.

ویژگی های زبان حساس به متن ویرایش

اجتماع، اشتراک، الحاق دو زبان حساس به متن، حساس به متن است، بسط کلینی یک زبان حساس به متن، حساس به متن است.^[۶]
مکمل یک زبان حساس به متن، حساس به متن است ^[۷] که در نتیجه به عنوان قضیهٔ Immerman–Szelepcsényi شناخته می‌شود.
هر زبان مستقل از متن که شامل رشتهٔ تهی نباشد، حساس به متن است.^[۸]
عضویت یک رشته در یک زبان که توسط گرامر حساس به متن دلخواه تعریف می‌شود یا توسط گرامر حساس به متن قطعی دلخواه تعریف می‌شود، از مسائل PSPACE- کامل می‌باشند.

جستار های وابسته ویرایش

وراثت چامسکی
آتاماتای خطی کران‌دار
زبان نمایه‌سازی‌شده - یک زیر مجموعه از زبان‌های حساس به متن
ماشین پشته‌ای جاسازی‌شده

منابع ویرایش

↑ Rothe, Jörg (2005), Complexity theory and cryptology, Texts in Theoretical Computer Science. An EATCS Series, Berlin: Springer-Verlag, p. 77, ISBN 978-3-540-22147-0, MR 2164257.
↑ Odifreddi, P. G. (1999), Classical recursion theory. Vol. II, Studies in Logic and the Foundations of Mathematics, vol. 143, Amsterdam: North-Holland Publishing Co., p. 236, ISBN 0-444-50205-X, MR 1718169.
↑ Pullum, Geoffrey K. (1983). Context-freeness and the computer processing of human languages. Proc. 21st Annual Meeting of the ACL.
↑ Bach, E. (1981). "Discontinuous constituents in generalized categorial grammars" بایگانی‌شده در ۲۱ ژانویه ۲۰۱۴ توسط Wayback Machine. NELS, vol. 11, pp. 1–12.
↑ Joshi, A.; Vijay-Shanker, K.; and Weir, D. (1991). "The convergence of mildly context-sensitive grammar formalisms". In: Sells, P., Shieber, S.M. and Wasow, T. (Editors). Foundational Issues in Natural Language Processing. Cambridge MA: Bradford.
↑ John E. Hopcroft, Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley.{{cite book}}: نگهداری یادکرد:استفاده از پارامتر نویسندگان (link); Exercise 9.10, p.230. In the 2003 edition, the chapter on context-sensitive languages has been omitted.
↑ Immerman, Neil (1988). "Nondeterministic Space is Closed under Complementation". SIAM Journal on Computing. 17 (5): 935–938. doi:10.1137/0217058. ISSN 0097-5397.
↑ (Hopcroft, Ullman, 1979); Theorem 9.9 b, p.228

Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.

[1] Rothe, Jörg (2005), Complexity theory and cryptology, Texts in Theoretical Computer Science. An EATCS Series, Berlin: Springer-Verlag, p. 77, ISBN 978-3-540-22147-0, MR 2164257.

[2] Odifreddi, P. G. (1999), Classical recursion theory. Vol. II, Studies in Logic and the Foundations of Mathematics, vol. 143, Amsterdam: North-Holland Publishing Co., p. 236, ISBN 0-444-50205-X, MR 1718169.

[3] Pullum, Geoffrey K. (1983). Context-freeness and the computer processing of human languages. Proc. 21st Annual Meeting of the ACL.

[4] Bach, E. (1981). "Discontinuous constituents in generalized categorial grammars" بایگانی‌شده در ۲۱ ژانویه ۲۰۱۴ توسط Wayback Machine. NELS, vol. 11, pp. 1–12.

[5] Joshi, A.; Vijay-Shanker, K.; and Weir, D. (1991). "The convergence of mildly context-sensitive grammar formalisms". In: Sells, P., Shieber, S.M. and Wasow, T. (Editors). Foundational Issues in Natural Language Processing. Cambridge MA: Bradford.

[6] John E. Hopcroft, Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley.{{cite book}}: نگهداری یادکرد:استفاده از پارامتر نویسندگان (link); Exercise 9.10, p.230. In the 2003 edition, the chapter on context-sensitive languages has been omitted.

[7] Immerman, Neil (1988). "Nondeterministic Space is Closed under Complementation". SIAM Journal on Computing. 17 (5): 935–938. doi:10.1137/0217058. ISSN 0097-5397.

[8] (Hopcroft, Ullman, 1979); Theorem 9.9 b, p.228

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]