المخروط (اللغات الرسمية)

في نظرية اللغات الرسمية ، يُعرَّف المخروط بأنه مجموعة من اللغات الرسمية التي تتمتع ببعض خصائص الإغلاق المرغوبة ، والتي تتميز بها بعض مجموعات اللغات المعروفة، ولا سيما عائلات اللغات المنتظمة ، واللغات الخالية من السياق، واللغات القابلة للتعداد التكراري . ^{[ 1 ]} يُعد مفهوم المخروط مفهومًا أكثر تجريدًا يشمل جميع هذه العائلات. وهناك مفهوم مشابه هو المخروط الأمين ، بشروط أقل صرامة. فعلى سبيل المثال، لا تُشكِّل اللغات الحساسة للسياق مخروطًا، ولكنها مع ذلك تمتلك الخصائص المطلوبة لتشكيل مخروط أمين.

مصطلح " المخروط" ذو أصل فرنسي. في الأدبيات ذات التوجه الأمريكي، يُشار عادةً إلى " ثلاثي كامل ". ويتوافق الثلاثي مع "المخروط المخلص".

المخروط عائلة${\displaystyle {\mathcal {S}}}$من اللغات بحيث${\displaystyle {\mathcal {S}}}$يحتوي على لغة واحدة على الأقل غير فارغة، ولأي${\displaystyle L\in {\mathcal {S}}}$حول بعض الحروف الأبجدية${\displaystyle \Sigma }$،

• لو${\displaystyle h}$هو تشاكل من${\displaystyle \Sigma ^{\ast }}$إلى البعض${\displaystyle \Delta ^{\ast }}$اللغة${\displaystyle h(L)}$هو في${\displaystyle {\mathcal {S}}}$؛
• لو${\displaystyle h}$هو تشاكل من بعض${\displaystyle \Delta ^{\ast }}$ل${\displaystyle \Sigma ^{\ast }}$اللغة${\displaystyle h^{-1}(L)}$هو في${\displaystyle {\mathcal {S}}}$؛
• لو${\displaystyle R}$هل أي لغة منتظمة${\displaystyle \Sigma }$، ثم${\displaystyle L\cap R}$هو في${\displaystyle {\mathcal {S}}}$.

توجد عائلة جميع اللغات المنتظمة داخل أي مخروط.

إذا قصرنا التعريف على التشاكلات التي لا تُدخل الكلمة الفارغة${\displaystyle \lambda }$عندئذٍ يُشار إلى المخروط الأمين ؛ ولا تكون التشاكلات العكسية مقيدة. ضمن التسلسل الهرمي لتشومسكي ، تُعتبر اللغات المنتظمة، واللغات الخالية من السياق، واللغات القابلة للتعداد التكراري جميعها مخاريط، بينما تُعتبر اللغات الحساسة للسياق واللغات التكرارية مخاريط أمينة فقط.

المحول ذو الحالة المحدودة هو آلة حالة محدودة لها مدخلات ومخرجات. وهو يُعرّف عملية التحويل.${\displaystyle T}$رسم خريطة للغة${\displaystyle L}$تحويل الأبجدية المدخلة إلى لغة أخرى${\displaystyle T(L)}$على أبجدية الإخراج. يمكن تنفيذ كل عملية من عمليات المخروط (التشاكل، والتشاكل العكسي، والتقاطع مع لغة منتظمة) باستخدام محول حالة محدود. وبما أن محولات الحالة المحدودة مغلقة تحت التركيب، فإنه يمكن تنفيذ أي تسلسل من عمليات المخروط بواسطة محول حالة محدود.

وعلى العكس من ذلك، فإن كل عملية تحويل حالة محدودة${\displaystyle T}$يمكن تحليلها إلى عمليات مخروطية. في الواقع، يوجد شكل طبيعي لهذا التحليل، ^{[ 2 ]} وهو ما يُعرف باسم نظرية نيفات : ^{[ 3 ]} أي أن كل عملية من هذا النوع${\displaystyle T}$يمكن تحليلها بشكل فعال على النحو التالي ${\displaystyle T(L)=g(h^{-1}(L)\cap R)}$، أين${\displaystyle g,h}$هي تشاكلات، و${\displaystyle R}$هي لغة منتظمة تعتمد فقط على${\displaystyle T}$.

باختصار، هذا يعني أن عائلة اللغات تُشكّل مخروطًا إذا وفقط إذا كانت مغلقة تحت عمليات التحويل ذات الحالات المحدودة. هذه مجموعة عمليات بالغة الأهمية. على سبيل المثال، يُمكن بسهولة كتابة مُحوِّل حالات محدودة (غير حتمي) باستخدام أبجدية.${\displaystyle \{a,b\}}$هذا يزيل كل ثانية${\displaystyle b}$في الكلمات ذات الطول الزوجي (ولا تُغير الكلمات الأخرى). وبما أن اللغات الخالية من السياق تُشكل مخروطًا، فإنها تكون مغلقة تحت هذه العملية غير المألوفة.

• عائلة اللغات المجردة

• جينسبيرغ، سيمور؛ جريباخ، شيلا (1967). "عائلات اللغات المجردة". وقائع مؤتمر الندوة السنوية الثامنة لعام 1967 حول نظرية التبديل والأتمتة، 18-20 أكتوبر 1967، أوستن، تكساس، الولايات المتحدة الأمريكية . معهد مهندسي الكهرباء والإلكترونيات. الصفحات 128-139 . 

• نيفات، موريس (1968). "تحويلات لغات تشومسكي" . حوليات معهد فورييه . 18 (1): 339-455 . دوى : 10.5802/aif.287 .
• سيمور جينسبيرغ ، الخصائص الجبرية وخصائص نظرية الأوتوماتا للغات الرسمية ، نورث هولاند، 1975، رقم ISBN 0-7204-2506-9.
• جون إي. هوبكروفت وجيفري دي. أولمان ، مقدمة في نظرية الأوتوماتا واللغات والحوسبة ، دار نشر أديسون-ويسلي، ريدينغ، ماساتشوستس، 1979. ISBN 0-201-02988-Xالفصل 11: خصائص الإغلاق لعائلات اللغات.
• ماتيسكو، الكسندرو؛ سالوما ، أرتو (1997). “الفصل الرابع: جوانب نظرية اللغة الكلاسيكية”. وفي روزنبرغ، غريزيغورز؛ سالوما، أرتو (محرران). دليل اللغات الرسمية. المجلد الأول: الكلمة، اللغة، النحو . سبرينغر-فيرلاغ. ص 175 – 252. ISBN  3-540-61486-9.

• موسوعة الرياضيات: تريو ، سبرينغر.