الشكل الطبيعي لكورودا
في نظرية اللغة الرسمية ، تكون القواعد النحوية غير المتقلصة في شكل كورودا الطبيعي إذا كانت جميع قواعد الإنتاج على الشكل التالي: [ 1 ]
- AB → CD أو
- أ → ب ج أو
- أ → ب أو
- أ → أ
حيث A وB وC وD رموز غير طرفية ، و a رمز طرفي . [ 1 ] بعض المصادر تحذف النمط A → B. [ 2 ]
سميت هذه اللغة نسبة إلى سيغي-يوكي كورودا ، الذي أطلق عليها في الأصل اسم القواعد الخطية المحدودة ، وهو مصطلح استخدمه أيضاً عدد قليل من المؤلفين الآخرين بعد ذلك. [ 3 ]
كل قاعدة نحوية في صيغة كورودا العادية غير منكمشة ، وبالتالي، تولد لغة حساسة للسياق . وعلى العكس من ذلك، يمكن تحويل كل قاعدة نحوية غير منكمشة لا تولد سلسلة فارغة إلى صيغة كورودا العادية. [ 2 ]
تُحوّل تقنية بسيطة تُنسب إلى جيورجي ريفيس قواعد اللغة في صيغة كورودا العادية إلى قواعد حساسة للسياق : حيث يُستبدل AB → CD بأربع قواعد حساسة للسياق هي AB → AZ و AZ → WZ و WZ → WD و WD → CD . وهذا يُثبت أن كل قواعد اللغة غير المتقلصة تُولّد لغة حساسة للسياق. [ 1 ]
يوجد شكل طبيعي مماثل للقواعد غير المقيدة أيضًا، والذي يسميه بعض المؤلفين على الأقل "شكل كورودا الطبيعي" أيضًا: [ 4 ]
- AB → CD أو
- أ → ب ج أو
- أ → أ أو
- A → ε
حيث ε هي السلسلة الفارغة. كل قواعد نحوية غير مقيدة مكافئة بشكل ضعيف لقواعد تستخدم فقط قواعد إنتاج من هذا الشكل. [ 2 ]
إذا حُذفت القاعدة AB → CD من المعادلة أعلاه، نحصل على قواعد نحوية خالية من السياق في صيغة تشومسكي المعيارية . [ 5 ] تُعد صيغة بنتونين المعيارية (للقواعد النحوية غير المقيدة) حالة خاصة حيث تكون القاعدة الأولى أعلاه هي AB → AD . [ 4 ] وبالمثل، بالنسبة للقواعد النحوية الحساسة للسياق، فإن صيغة بنتونين المعيارية، والتي تُسمى أيضًا الصيغة المعيارية أحادية الجانب (وفقًا لمصطلحات بنتونين نفسه)، هي: [ 1 ] [ 2 ]
- AB → AD أو
- أ → ب ج أو
- أ → أ
لكل قواعد نحوية حساسة للسياق، يوجد شكل طبيعي أحادي الجانب مكافئ ضعيفًا. [ 2 ]
انظر أيضاً
مراجع
- 1 2 3 4 ماسامي إيتو؛ يوجي كوباياشي؛ كونيتاكا شوجي (2010). الأوتوماتا واللغات الرسمية والأنظمة الجبرية: وقائع AFLAS 2008، كيوتو، اليابان، 20-22 سبتمبر 2008 . العلمية العالمية. ص. 182. ردمك 978-981-4317-60-3.
- 1 2 3 4 5 ماتيسكو، ألكسندرو؛ سالوما ، أرتو (1997). “الفصل الرابع: جوانب نظرية اللغة الكلاسيكية”. وفي روزنبرغ، غريزيغورز؛ سالوما، أرتو (محرران). دليل اللغات الرسمية. المجلد الأول: الكلمة، اللغة، النحو . سبرينغر-فيرلاغ. ص. 190. ردمك 978-3-540-61486-9.
- ↑ ويليم جيه إم ليفيلت (2008). مقدمة في نظرية اللغات الرسمية والأتمتة . دار نشر جون بنجامينز. الصفحات 126-127 . ISBN 978-90-272-3250-2.
- 1 2 ألكسندر ميدونا (2000). الأوتوماتا واللغات: النظرية والتطبيقات . سبرينغر ساينس آند بيزنس ميديا. ص 722. ISBN 978-1-85233-074-3.
- ↑ ألكسندر ميدونا (2000). الأوتوماتا واللغات: النظرية والتطبيقات . سبرينغر ساينس آند بيزنس ميديا. ص 728. ISBN 978-1-85233-074-3.
للمزيد من القراءة
- سيج-يوكي كورودا (يونيو 1964). "فئات اللغات والآلات الخطية المحدودة" . المعلومات والتحكم . 7 (2): 207-223 . doi : 10.1016/S0019-9958(64)90120-2 .
- G. Révész، "تعليق على الورقة "اكتشاف الأخطاء في اللغات الرسمية،" مجلة علوم الكمبيوتر والنظام، المجلد. 8، لا. 2، الصفحات من 238 إلى 242، أبريل 1974. دوى : 10.1016/S0022-0000(74)80057-7 (خدعة ريفيسز)
- بنتونين، مارتي (أغسطس 1974). "السياق أحادي الجانب وثنائي الجانب في القواعد الرسمية" . المعلومات والتحكم . 25 (4): 371-392 . doi : 10.1016/S0019-9958(74)91049-3 .
- اللغات الرسمية