إذا تم ترك Grammar G ومناسبا، فلماذا $ || L (G) ||\ leq || p || $؟
-
29-09-2020 - |
سؤال
كنت أدرس نظرية أتمتة اللغات الرسمية ومرجع هذا السؤال:
إذا كانت قواعد اللغة $ G $ تم تركها ومناسبا، لماذا $ || l (g) || \ leq || p || $ ؟
بحثت عن النظرية لكنني أفتقد شيئا ما. وأنا غير قادر على العثور على الجواب في أي مكان، لذلك أطلب هنا.
التعاريف:
$ P $ = مجموعة من القواعد
القاعدة المنتظمة اليمنى: قواعد اللغة $ g= (n، t، p، s) $ ، قاعدة في $ p $ إذا كانت القاعدة في النموذج: $ a \ charnarrow ba $ $ (a، B \ in n) \ Wedge (a \ in t) $
القاعدة العادية اليسرى: قواعد اللغة $ g= (n، t، p، s) $ ، قاعدة في $ p $ إذا كانت القاعدة في النموذج: $ a \ charnarrow ab $ $ (a، ب \ في ن) \ Wedge (a \ in t) $ .
grammar العادية اليسرى: قواعد نحوية حيث تكون جميع القواعد قواعد عادية اليسار.
grammar العادية اليمنى: قواعد قواعد حيث تكون جميع القواعد قواعد منتظمة مناسبة.
مثال على مجموعة قاعدة $ P $ مع كل من القواعد الأساسية والمنتظمة اليمنى: $ p={a \ ignarrow a، b \ charnarrow b \} $
ويجعل كل من الأيسر العادية والجدية العادية تجعل القواعد العادية والنوع 3
المحلول
grammar الخاص بك يحتوي فقط على قواعد النموذج $ a \ t $ ، ل $ a \ in n $ و $ a \ in t .لذلك $ l (g)={\ sigma \ in t: s \ to \ sigma \ in p \} $ .أنت تأخذ من هنا.