التسلسل الهرمي لتشومسكي

📅 آخر تحديث: ٢٩ يوليو ٢٠٢٦
✍️ نُشر في: ٢٩ يوليو ٢٠٢٦
📷 يحتوي على 27 صور
الموسوعة الحرة
التسلسل الهرمي لتشومسكي
المجموعات المضمنة الموصوفة في التسلسل الهرمي لتشومسكي

يُعدّ التسلسل الهرمي لتشومسكي، في مجالات نظرية اللغات الرسمية وعلوم الحاسوب واللغويات، تسلسلاً هرمياً احتواءً لفئات القواعد النحوية الرسمية . تصف القاعدة النحوية الرسمية كيفية تكوين سلاسل نصية من أبجدية لغة رسمية، بحيث تكون هذه السلاسل صحيحة وفقاً لقواعد اللغة . وقد افترض اللغوي نعوم تشومسكي وجود أربع فئات مختلفة من القواعد النحوية الرسمية، قادرة على توليد لغات متزايدة التعقيد. كما يمكن لكل فئة توليد لغة جميع الفئات الأدنى منها (بما في ذلك المجموعة).

تاريخ

وُصفت الفكرة العامة لتسلسل القواعد النحوية لأول مرة من قِبل نعوم تشومسكي في كتابه "ثلاثة نماذج لوصف اللغة" خلال عملية صياغة القواعد النحوية التحويلية التوليدية (TGG). [ 1 ] كما لعب مارسيل بول شوتزنبرغر دورًا في تطوير نظرية اللغات الرسمية ؛ إذ تصف ورقته البحثية "النظرية الجبرية للغات الخالية من السياق" [ 2 ] التسلسل الهرمي الحديث، بما في ذلك القواعد النحوية الخالية من السياق. [ 3 ]

بشكل مستقل، وبالتوازي مع اللغويين، كان علماء الرياضيات يطورون نماذج للحوسبة (عبر الأوتوماتا ). إن تحليل الجملة في لغة ما يشبه الحوسبة، وقد أثبتت القواعد النحوية التي وصفها تشومسكي أنها تشبه نماذج الآلات المختلفة وتتكافئ معها في القدرة الحسابية. [ 4 ]

التسلسل الهرمي

يلخص الجدول التالي كل نوع من أنواع قواعد تشومسكي الأربعة، وفئة اللغة التي تولدها، ونوع الآلة التي تتعرف عليها، والشكل الذي يجب أن تتخذه قواعدها. وتُحدد الفئات من خلال القيود المفروضة على قواعد الإنتاج .

قواعد اللغةاللغاتالتعرف على الآلاتقواعد الإنتاج (القيود) [ أ ]أمثلة [ 5 ] [ 6 ]
النوع 3عاديآلة الحالة المحدودةأ→أ{\displaystyle A\rightarrow {\text{a}}}أ→أب{\displaystyle A\rightarrow {\text{a}}B}(يمين عادي) أوأ→أ{\displaystyle A\rightarrow {\text{a}}}أ→بأ{\displaystyle A\rightarrow B{\text{a}}}(يسار عادي)ل={أن|ن>0}{\displaystyle L=\{a^{n}\mid n>0\}}
النوع الثانيبدون سياقآلة دفع غير حتميةأ→α{\displaystyle A\rightarrow \alpha }ل={أنبن|ن>0}{\displaystyle L=\{a^{n}b^{n}\mid n>0\}}
النوع 1حساس للسياقآلة تورينغ غير حتمية ذات حدود خطيةαأβ→αγβ{\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }ل={أنبنجن|ن>0}{\displaystyle L=\{a^{n}b^{n}c^{n}\mid n>0\}}
النوع 0قابل للتعداد بشكل متكررآلة تورينجγ→α{\displaystyle \gamma \rightarrow \alpha }(γ{\displaystyle \gamma }(غير فارغ)ل={w|w{\displaystyle L=\{w\mid w}يصف آلة تورينج المنتهية}{\displaystyle \}}
  1. ↑ معنى الرموز:
    • أ{\displaystyle {\text{a}}}= طرفي
    • أ{\displaystyle A}،ب{\displaystyle B}= غير طرفي
    • α{\displaystyle \alpha }،β{\displaystyle \beta }،γ{\displaystyle \gamma }= سلسلة من الرموز الطرفية و/أو غير الطرفية

لاحظ أن مجموعة القواعد النحوية المقابلة للغات المتكررة ليست عضواً في هذا التسلسل الهرمي؛ ستكون هذه بشكل صحيح بين النوع 0 والنوع 1.

كل لغة منتظمة خالية من السياق، وكل لغة خالية من السياق حساسة للسياق، وكل لغة حساسة للسياق قابلة للتكرار، وكل لغة قابلة للتكرار قابلة للتعداد التكراري. هذه كلها حالات تضمين صحيحة، بمعنى أنه توجد لغات قابلة للتعداد التكراري ليست حساسة للسياق، ولغات حساسة للسياق ليست خالية من السياق، ولغات خالية من السياق ليست منتظمة. [ 7 ]

القواعد النحوية المنتظمة (النوع 3)

تُنتج قواعد النوع الثالث اللغات المنتظمة . تُقيد هذه القواعد قواعدها برمز غير طرفي واحد على الجانب الأيسر وجانب أيمن يتكون من رمز طرفي واحد، قد يتبعه رمز غير طرفي واحد، وفي هذه الحالة تكون القاعدة منتظمة من اليمين . بدلاً من ذلك، يمكن أن تتكون جميع القواعد من رمز طرفي واحد على الجانب الأيمن، قد يسبقه رمز غير طرفي واحد ( منتظمة من اليسار ). تُنتج هذه القواعد نفس اللغات. مع ذلك، إذا جُمعت القواعد المنتظمة من اليسار والقواعد المنتظمة من اليمين، فإن اللغة لا تُشترط أن تكون منتظمة.S→ε{\displaystyle S\rightarrow \varepsilon }يُسمح به هنا أيضًا إذاS{\displaystyle S}لا تظهر هذه اللغة على الجانب الأيمن من أي قاعدة. وهي تحديدًا جميع اللغات التي يمكن تحديدها بواسطة آلة حالة محدودة . بالإضافة إلى ذلك، يمكن الحصول على هذه المجموعة من اللغات الرسمية باستخدام التعابير النمطية . تُستخدم اللغات النمطية عادةً لتحديد أنماط البحث والبنية المعجمية للغات البرمجة.

على سبيل المثال، اللغة المنتظمةل={أن|ن>0}{\displaystyle L=\{a^{n}\mid n>0\}}يتم توليدها بواسطة قواعد اللغة من النوع 3جي=({S}،{أ}،P،S){\displaystyle G=(\{S\},\{a\},P,S)}مع الإنتاجاتP{\displaystyle P}وهي كالتالي.

S → aS
S → a

في علم اللغة ، تُسمى اللغة غير المنتظمة لغة فوق منتظمة . [ 8 ] [ 9 ]

القواعد النحوية الخالية من السياق (النوع 2)

تُنتج قواعد النوع الثاني اللغات الخالية من السياق . وتُعرَّف هذه اللغات بقواعد من الشكل التالي:أ→α{\displaystyle A\rightarrow \alpha }معأ{\displaystyle A}كونه غير طرفي وα{\displaystyle \alpha }كونها سلسلة من الرموز الطرفية و/أو غير الطرفية. هذه اللغات هي تحديدًا جميع اللغات التي يمكن التعرف عليها بواسطة آلة دفع غير حتمية . تُعدّ اللغات الخالية من السياق - أو بالأحرى مجموعتها الفرعية من اللغات الحتمية الخالية من السياق - الأساس النظري لبنية العبارات في معظم لغات البرمجة ، على الرغم من أن تحليلها الدلالي يتضمن حل الأسماء الحساس للسياق بسبب التصريحات والنطاق . غالبًا ما تُستخدم مجموعة فرعية من القواعد النحوية لتسهيل التحليل، كما هو الحال في محلل LL .

على سبيل المثال، اللغة الخالية من السياق ل={أنبن|ن>0}{\displaystyle L=\{a^{n}b^{n}\mid n>0\}}يتم توليدها بواسطة قواعد اللغة من النوع الثانيجي=({S}،{أ،ب}،P،S){\displaystyle G=(\{S\},\{a,b\},P,S)}مع الإنتاجاتP{\displaystyle P}وهي كالتالي.

S → aSb
S → ab

اللغة خالية من السياق ولكنها ليست منتظمة (بحسب نظرية الضخ للغات المنتظمة ).

يمكن توليد كل لغة خالية من السياق بواسطة قواعد نحوية في شكل تشومسكي الطبيعي .

القواعد النحوية الحساسة للسياق (النوع 1)

تُنتج قواعد النوع الأول لغات حساسة للسياق . تحتوي هذه القواعد على قواعد من الشكل التالي:αأβ→αγβ{\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }معأ{\displaystyle A}رمز غير طرفي وα{\displaystyle \alpha }،β{\displaystyle \beta }وγ{\displaystyle \gamma }سلاسل من الرموز الطرفية و/أو غير الطرفية. السلاسلα{\displaystyle \alpha }وβ{\displaystyle \beta }قد تكون فارغة، ولكنγ{\displaystyle \gamma }يجب أن تكون غير فارغة. القاعدةS→ϵ{\displaystyle S\rightarrow \epsilon }يُسمح بذلك إذاS{\displaystyle S}لا يظهر على الجانب الأيمن من أي قاعدة. اللغات التي تصفها هذه القواعد النحوية هي بالضبط جميع اللغات التي يمكن التعرف عليها بواسطة آلة خطية محدودة (آلة تورينغ غير حتمية يكون شريطها محدودًا بثابت مضروب في طول المدخلات).

على سبيل المثال، اللغة الحساسة للسياق ل={أنبنجن|ن>0}{\displaystyle L=\{a^{n}b^{n}c^{n}\mid n>0\}}يتم توليدها بواسطة قواعد اللغة من النوع الأولجي=({S،أ،ب،ج،دبليو،Z}،{أ،ب،ج}،P،S){\displaystyle G=(\{S,A,B,C,W,Z\},\{a,b,c\},P,S)}مع الإنتاجاتP{\displaystyle P}وهي كالتالي.

S → aBC
S → aSBC
CB → CZ
CZ → WZ
WZ → WC
WC → BC
aB → ab
bB → bb
bC → bc
cC → cc

اللغة حساسة للسياق ولكنها ليست خالية من السياق (بحسب نظرية الضخ للغات الخالية من السياق ). ويُمكن إثبات أن هذه القواعد النحوية تُولّدل={أنبنجن|ن>0}{\displaystyle L=\{a^{n}b^{n}c^{n}\mid n>0\}}تم توضيح ذلك في المقال الخاص بالقواعد النحوية الحساسة للسياق .

القواعد النحوية القابلة للتعداد بشكل متكرر (النوع 0)

تشمل قواعد النوع صفر جميع القواعد الرسمية. لا توجد قيود على قواعد الإنتاج. تُولّد هذه القواعد جميع اللغات التي يمكن لآلة تورينج التعرف عليها ، وبالتالي، يمكن توليد أي لغة يُمكن توليدها بواسطة قواعد النوع صفر. [ 10 ] تُعرف هذه اللغات أيضًا باللغات القابلة للتعداد التكراري أو اللغات القابلة للتعرف عليها بواسطة تورينج . [ 10 ] تجدر الإشارة إلى أن هذا يختلف عن اللغات التكرارية ، التي يمكن تحديدها بواسطة آلة تورينج تتوقف دائمًا .

اللغات الطبيعية

عند البحث في مكانة اللغة الطبيعية في هرم تشومسكي، تبين في خمسينيات القرن الماضي أن اللغة الطبيعية ليست منتظمة. [ 11 ] على سبيل المثال، تحتوي اللغة الإنجليزية على تراكيب تضمين مركزية ، مما يعني أنها لا يمكن أن تكون منتظمة. [ 8 ] [ 9 ] بتعبير أدق، فإن الحجة هي أن اللغة

ل={أنبمجمدن|ن،م>0}{\displaystyle L=\{a^{n}b^{m}c^{m}d^{n}\mid n,m>0\}}

ليست منتظمة، وهو ما يمكن إثباته باستخدام نظرية الضخ للغات الخالية من السياق . في العقود اللاحقة، تبين أن اللغة الطبيعية ليست خالية من السياق أيضًا، وذلك باستخدام مثال التبعيات التسلسلية المتبادلة في الألمانية السويسرية . [ 12 ] [ 13 ] في هذه الحالة، تتمثل الحجة في أن اللغة

ل={أنبمجندم|ن،م>0}{\displaystyle L=\{a^{n}b^{m}c^{n}d^{m}\mid n,m>0\}}

ليس خالياً من السياق.

الاقتباسات

  1. ↑ تشومسكي 1956 .
  2. ↑ تشومسكي وشوتزنبرغر 1963 .
  3. ↑ ألوت، نيكولاس؛ لوندال، تيرجي؛ ري، جورج (27 أبريل 2021). "مقدمة موجزة". دليل تشومسكي . ص 1-17 . doi : 10.1002/9781119598732.ch1 . ISBN  9781119598701. S2CID 241301126 . 
  4. ↑ كوزين، ديكستر سي. (2007). الأوتوماتا والحوسبة . نصوص جامعية في علوم الحاسوب. سبرينغر. ص 3-4 . ISBN  978-0-387-94907-9.
  5. ↑ جيفرز، هـ.؛ روت، ج. (2016). "التطبيقات، التسلسل الهرمي لتشومسكي، والملخص" (ملف PDF) . اللغات المنتظمة . مؤرشف (ملف PDF) من الأصل بتاريخ 19-11-2018.
  6. ↑ سودكامب، توماس أ. (1997) [1988]. اللغات والآلات: مقدمة في نظرية علوم الحاسوب . ريدينغ، ماساتشوستس، الولايات المتحدة الأمريكية: أديسون ويسلي لونغمان. ص 310. ISBN  978-0-201-82136-9.
  7. ↑ تشومسكي، نعوم (1963). "الفصل 12: الخصائص الشكلية للقواعد النحوية". في: لوس، ر. دنكان؛ بوش، روبرت ر.؛ جالانتير، يوجين (محررون). دليل علم النفس الرياضي . المجلد الثاني. جون وايلي وأولاده، الصفحات 323-418 .  
  8. 1 2 ياغر، جيرهارد؛ روجرز، جيمس (2012). "نظرية اللغة الرسمية: تحسين التسلسل الهرمي لتشومسكي" . المعاملات الفلسفية للجمعية الملكية ب . 367 : 1956-1970 . doi : 10.1098/rstb.2012.00777 .
  9. 1 2 فيتش، دبليو. تيكومسيه؛ فريديريتشي، أنجيلا د. (2012). "التعلم الاصطناعي للقواعد النحوية يلتقي بنظرية اللغة الرسمية: نظرة عامة" . المعاملات الفلسفية للجمعية الملكية ب . 367 : 1933-1955 . doi : 10.1098/rstb.2012.0103 .
  10. 1 2 سيبسر، مايكل ( 1997). مقدمة في نظرية الحوسبة ( الطبعة الأولى). سينجايج ليرنينج. ص 130. ISBN   0-534-94728-Xأطروحة تشيرش-تورينغ
  11. ↑ تشومسكي، نعوم (1957). البنى النحوية . موتون وشركاه.
  12. ^ هويجبريتس ، ريني (1984). “القصور الضعيف في قواعد بنية العبارة الخالية من السياق”. في دي هان، جير؛ تروميل، ميكي؛ زونيفيلد، ويم (محرران). فان بيريفيري نار كيرن . فوريس. ص 81 – 99. 
  13. ↑ شيبر، ستيوارت م. (1985). "أدلة ضد عدم ارتباط اللغة الطبيعية بالسياق" . اللغويات والفلسفة . 8 : 333-343 . doi : 10.1007/BF00630917 .

مراجع