لغة ديك

في نظرية اللغات الرسمية لعلوم الحاسوب والرياضيات واللغويات ، تُعرَّف كلمة دايك بأنها سلسلة متوازنة من الأقواس. وتشكل مجموعة كلمات دايك لغة دايك . أبسطها، دايك-1، تستخدم قوسين متطابقين فقط، مثل ( و ).

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

يترك${\displaystyle \Sigma =\{[,]\}}$ليكن الأبجدية التي تتكون من الرموز [ و ].${\displaystyle \Sigma ^{*}}$يُشير إلى إغلاق كلين الخاص به . تُعرَّف لغة ديك على النحو التالي:

${\displaystyle \{u\in \Sigma ^{*}\vert {\text{ جميع بادئات }}u{\text{ لا تحتوي على عدد من ] أكثر من عدد [}}{\text{ وعدد [ في }}u{\text{ يساوي عدد ]}}\}.}$

• لغة ديك مغلقة تحت عملية الربط .
• عن طريق العلاج${\displaystyle \Sigma ^{*}}$باعتبارنا أحاديًا جبريًا تحت التسلسل، نرى أن بنية الأحادي تنتقل إلى خارج القسمة${\displaystyle \Sigma ^{*}/R}$مما ينتج عنه أحادي التركيب النحوي للغة ديك . الفئة${\displaystyle \operatorname {Cl} (\epsilon )}$سيتم الإشارة إلى${\displaystyle 1}$.
• الزمرة النحوية للغة ديك ليست تبديلية : إذا${\displaystyle u=\operatorname {Cl} ([)}$و${\displaystyle v=\operatorname {Cl} (])}$ثم${\displaystyle uv=\operatorname {Cl} ([])=1\neq \operatorname {Cl} (][)=vu}$.
• باستخدام الرموز المذكورة أعلاه،${\displaystyle uv=1}$لكن لا هذا ولا ذاك${\displaystyle u}$ولا${\displaystyle v}$قابلة للعكس في${\displaystyle \Sigma ^{*}/R}$.
• تتشابه المجموعة التركيبية الأحادية للغة ديك مع المجموعة شبه الدورية الثنائية بفضل خصائص${\displaystyle \operatorname {Cl} ([)}$و${\displaystyle \operatorname {Cl} (])}$كما هو موضح أعلاه.
• بحسب نظرية تمثيل تشومسكي-شوتزنبرغر ، فإن أي لغة خالية من السياق هي صورة متماثلة لتقاطع لغة منتظمة مع لغة ديك على نوع واحد أو أكثر من أزواج الأقواس. ^{[ 2 ]}
• يمكن التعرف على لغة ديك، التي تحتوي على نوعين متميزين من الأقواس، في فئة التعقيد.${\displaystyle TC^{0}}$[ ^{3 ]​}
• عدد كلمات دايك المميزة التي تحتوي على n زوجًا من الأقواس و k زوجًا من الأقواس الداخلية (أي السلسلة الفرعية )${\displaystyle [\ ]}$) هو رقم نارايانا${\displaystyle \operatorname {N} (n,k)}$.
• كلمات ديك متماثلة مع مسارات ديك ، وهي مجموعة فرعية من رموز مسار الدرج.
• عدد كلمات ديك المختلفة التي تحتوي على n زوجًا من الأقواس بالضبط هو العدد الكاتالاني رقم n${\displaystyle C_{n}}$لاحظ أن لغة ديك للكلمات التي تحتوي على n زوجًا من الأقواس تساوي اتحاد لغات ديك للكلمات التي تحتوي على n زوجًا من الأقواس مع k زوجًا داخليًا ، وذلك على جميع قيم k الممكنة ، كما هو مُعرَّف في النقطة السابقة. وبما أن k يمكن أن تتراوح من 0 إلى n ، فإننا نحصل على المساواة التالية، وهي صحيحة بالفعل:

${\displaystyle C_{n}=\sum _{k=1}^{n}\operatorname {N} (n,k)}$

يمكننا تعريف علاقة تكافؤ${\displaystyle L}$حول لغة ديك${\displaystyle {\mathcal {D}}}$. ل${\displaystyle u,v\in {\mathcal {D}}}$لدينا${\displaystyle (u,v)\in L}$إذا وفقط إذا${\displaystyle |u|=|v|}$، أي${\displaystyle u}$و${\displaystyle v}$لها نفس الطول. هذه العلاقة تقسم لغة ديك:${\displaystyle {\mathcal {D}}/L=\{{\mathcal {D}}_{0},{\mathcal {D}}_{1},\ldots \}}$لدينا${\displaystyle {\mathcal {D}}={\mathcal {D}}_{0}\cup {\mathcal {D}}_{2}\cup {\mathcal {D}}_{4}\cup \ldots =\bigcup _{n=0}^{\infty }{\mathcal {D}}_{n}}$أين${\displaystyle {\mathcal {D}}_{n}=\{u\in {\mathcal {D}}\mid |u|=n\}}$. لاحظ أن${\displaystyle {\mathcal {D}}_{n}}$فارغ للأعداد الفردية${\displaystyle n}$.

بعد تقديم كلمات دايك ذات الطول${\displaystyle n}$يمكننا إقامة علاقة بينهما. لكل${\displaystyle n\in \mathbb {N} }$نُعرّف علاقة${\displaystyle S_{n}}$على${\displaystyle {\mathcal {D}}_{n}}$؛ ل${\displaystyle u,v\in {\mathcal {D}}_{n}}$لدينا${\displaystyle (u,v)\in S_{n}}$إذا وفقط إذا${\displaystyle v}$يمكن الوصول إليه من${\displaystyle u}$عن طريق سلسلة من عمليات التبديل المناسبة . تبديل مناسب باختصار${\displaystyle u\in {\mathcal {D}}_{n}}$يستبدل هذا الكود رمز '][' برمز '[]'. لكل${\displaystyle n\in \mathbb {N} }$العلاقة${\displaystyle S_{n}}$اصنع${\displaystyle {\mathcal {D}}_{n}}$إلى مجموعة مرتبة جزئياً . العلاقة${\displaystyle S_{n}}$هي انعكاسية لأن سلسلة فارغة من عمليات التبديل الصحيحة تأخذ${\displaystyle u}$ل${\displaystyle u}$وتترتب خاصية التعدي على ذلك لأنه يمكننا تمديد سلسلة من عمليات التبديل الصحيحة التي تأخذ${\displaystyle u}$ل${\displaystyle v}$عن طريق دمجها مع سلسلة من عمليات التبديل المناسبة التي تأخذ${\displaystyle v}$ل${\displaystyle w}$تشكيل تسلسل يأخذ${\displaystyle u}$داخل${\displaystyle w}$. لرؤية ذلك${\displaystyle S_{n}}$ولأنها أيضاً متناظرة عكسياً، فإننا نقدم دالة مساعدة${\displaystyle \sigma _{n}:{\mathcal {D}}_{n}\rightarrow \mathbb {N} }$يُعرَّف بأنه مجموع جميع البادئات${\displaystyle v}$ل${\displaystyle u}$:

${\displaystyle \sigma _{n}(u)=\sum _{vw=u}{\Big (}({\text{count of ['s in }}v)-({\text{count of ]'s in }}v){\Big )}}$

يوضح الجدول التالي أن${\displaystyle \sigma _{n}}$وهي رتيبة تمامًا فيما يتعلق بعمليات التبادل الصحيحة.

الرتابة الصارمة لـ${\displaystyle \sigma _{n}}$

المجاميع الجزئية لـ${\displaystyle \sigma _{n}(u)}$	${\displaystyle P}$	${\displaystyle P-1}$	${\displaystyle P}$	${\displaystyle Q}$
${\displaystyle u}$	${\displaystyle \ldots }$	]	[	${\displaystyle \ldots }$
${\displaystyle u'}$	${\displaystyle \ldots }$	[	]	${\displaystyle \ldots }$
المجاميع الجزئية لـ${\displaystyle \sigma _{n}(u')}$	${\displaystyle P}$	${\displaystyle P+1}$	${\displaystyle P}$	${\displaystyle Q}$
الفرق بين المجاميع الجزئية	0	2	0	0

لذلك${\displaystyle \sigma _{n}(u')-\sigma _{n}(u)=2>0}$لذا${\displaystyle \sigma _{n}(u)<\sigma _{n}(u')}$عندما يكون هناك تبادل مناسب يأخذ${\displaystyle u}$داخل${\displaystyle u'}$الآن إذا افترضنا أن كليهما${\displaystyle (u,v),(v,u)\in S_{n}}$و${\displaystyle u\neq v}$ثم توجد متواليات غير فارغة من عمليات التبديل المناسبة مثل${\displaystyle u}$يتم إدخاله في${\displaystyle v}$والعكس صحيح. ولكن بعد ذلك${\displaystyle \sigma _{n}(u)<\sigma _{n}(v)<\sigma _{n}(u)}$وهذا أمر غير منطقي. لذلك، عندما يكون كلاهما${\displaystyle (u,v)}$و${\displaystyle (v,u)}$في${\displaystyle S_{n}}$لدينا${\displaystyle u=v}$، لذلك${\displaystyle S_{n}}$متناظر عكسيًا.

المجموعة المرتبة جزئياً${\displaystyle D_{8}}$يظهر ذلك في الرسم التوضيحي المصاحب للمقدمة إذا فسرنا [ على أنه صعود و ] على أنه هبوط.

• توافق ديك
• كلمة شبكية

• لغة ديك في بلانيت ماث .
• برهان على نظرية تشومسكي شوتزنبرغر
• مقالة مدونة AMS حول كلمات ديك