الناسع الحرة مقابل السياق

Question

أنا أدرس لبلدي لغات الحوسبة اختبار، وهناك فكرة واحدة أواجه مشاكل في التفاف رأسي حولها.

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

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

هل يمكن لشخص مساعدتي وضع كل هذا معا؟

Answer 1

Grammar العادية إما خطي على اليمين أو الأيسر، في حين أن القواعد الحرة الحرة للسياق هي أساسا أي مزيج من المحطات وغير المحطات. وبالتالي يمكنك أن ترى أن النحو العادي هو مجموعة فرعية من القواعد الخالية من السياق.

لذلك بالنسبة إلى palindrome على سبيل المثال، هو من النموذج،

S->ABA
A->something
B->something

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

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

Answer 2

أعتقد أن ما تريد أن تفكر فيه هو مختلف Lemmata الضخ. يمكن التعرف على لغة منتظمة بواسطة Automaton Finite. تتطلب لغة خالية من السياق مجموعة مكدس، وتتطلب لغة حساسة للسياق حدودا (أي ما يعادل القول إنه يتطلب آلة تورينج كاملة.)

لذلك، إذا فكرنا في ضخ Lemma للغات العادية, ، ما يقول، هو أساسا، هو أن أي لغة منتظمة يمكن تقسيمها إلى ثلاث قطع، عاشر, Y., ، و z., ، حيث جميع حالات اللغة في XY * Z. (حيث * هو تكرار كلاين، أي 0 أو أكثر من نسخ Y..) هل لديك أساسا واحدة "غير حكومية" يمكن توسيعها.

الآن، ماذا عن لغات خالية من السياق؟ هناك مشابه ضخ Lemma للغات مع السياق الذي يكسر السلاسل في اللغة إلى خمسة أجزاء، uvxyz., ، وأين جميع حالات اللغة في الأشعة فوق البنفسجية^أناسي^أناz., ، لأني ≥ 0. الآن، لديك اثنين "غير الحرمينيات" التي يمكن تكرارها، أو ضخ، طالما لديك نفس العدد.

Answer 3

الفرق بين القواعد الحرة العادية والسياق:(n، σ، p، s): المحطات، onterminals، الإنتاج، بدء الرموز محطة الدولة

● الرموز الابتدائية للغة المعرفة من قبل قواعد رسمية

● ABC.

الرموز غير اليدوية (أو المتغيرات النحوية)

● استبدالها بمجموعات من الرموز الطرفية وفقا لقواعد الإنتاج

● ABC.

قواعد النحوية العادية أو اليسارية الناقدية العادية العادية، جميع القواعد تطيع النماذج

1. ب → أين ب هي غير ملمقة في N و A هي محطة في σ
2. ب → AC حيث b و c في n و a في σ
3. ب → ε من أين ب في n و ε يدل على السلسلة الفارغة، أي سلسلة الطول 0

غادر النحو العادي، جميع القواعد تطيع النماذج

1. a → أين a غير ملموس في n و a هو محطة في σ
2. A → BA حيث A و B في n و a في σ
3. → ε حيث يوجد في N و ε هي السلسلة الفارغة

القواعد الحرة السياق (CFG)

○ قواعد النحوية الرسمية التي تكون فيها كل قاعدة إنتاج من النموذج الخامس → W

○ v هو رمز واحد غير قادر

○ W هي سلسلة من المحطات و / أو غير متناغم (W. يمكن أن تكون فارغة)

Answer 4

التعبيرات العادية

• أساس التحليل المعجمي
• تمثل لغات منتظمة

القواعد الحرة السياق

• أساس التحليل
• تمثل بناء اللغة

Answer 5

Grammar العادية: - القواعد المحتوية على النحو التالي هو RG:

V->TV or VT
V->T

حيث v = المتغير و t = محطة

يمكن ترك RG قواعد اللغة الخطية أو النحو الأيمن، ولكن ليس قواعد اللغة الخطية المتوسطة.

كما نعلم أن جميع RG هي قواعد اللغة الخطية ولكن ترك النحو الخطي الخطي أو الأيمن فقط RG.

القواعد العادية يمكن غامضة.

S->aA|aB
A->a
B->a

Gmasguous Grammar: - للحصول على سلسلة X موجودة أكثر من LMD أو أكثر من RMD أو أكثر من شجرة تحليل واحدة أو LMD واحد وواحد من RMD واحد ولكن كلاهما ينتجن شجرة تحليل مختلفة.

                S                   S

              /   \               /   \
             a     A             a     B
                    \                   \
                     a                   a

هذا القواعد النحوية غامضة لأن اثنين من شجرة تحليل.

CFG: - وقال القواعد أن يكون CFG إذا كان إنتاجه في النموذج:

   V->@   where @ belongs to (V+T)*

DCFL:- كما نعرف كل DCFL (1) Grammar وجميع LL (1) هو LR (1) لذلك ليس غامضا أبدا. لذلك DCFG لا يكون غامضا أبدا.

نحن نعرف أيضا أن كل rl هي dcfl حتى rl أبدا غامضة. لاحظ أن RG قد يكون غامضا ولكن rl لا.

CFL: cfl قد أو لا غامضة.

ملحوظة: rl لا تكون غامضة بطبيعتها.

Answer 6

Grammar خالية من السياق إذا كانت جميع قواعد الإنتاج لها النموذج: أ (وهذا هو، يمكن أن يكون الجانب الأيسر من القاعدة متغيرا واحدا فقط؛ الجانب الأيمن غير مقيد ويمكن أن يكون أي تسلسل من المحطات والمتغيرات). يمكننا تحديد قواعد قواعدية ك 4 Tuple حيث V هي مجموعة محدودة (المتغيرات)، _ هي مجموعة محددة (محطات)، S هي المتغير Start، و R هي مجموعة محدودة من القواعد، كل منها رسم خرائط الخامس
Grammar العادية إما خطي على اليمين أو الأيسر، في حين أن القواعد الحرة الحرة للسياق هي أساسا أي مزيج من المحطات وغير المحطات. وبالتالي يمكننا القول أن القواعد العادية هي مجموعة فرعية من القواعد الخالية من السياق. بعد هذه الخصائص، يمكننا القول أن مجموعة السيارات المجانية للسياق تحتوي أيضا على مجموعة لغات منتظمة

Answer 7

Grammar العادية أساسا هو مجموعة فرعية من القواعد الحرة السياق، لكننا لا نستطيع أن نقول كل القواعد الحرة السياق هي قواعد النحوية العادية. أساسا السياق القواعد الحرة غامضة والقواعد العادية قد تكون غامضة.

Answer 8

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