تعريف اللغة العادية لنظرية الأتمتة. طرق تحديد اللغات العادية. الأبجدية، الكلمة، اللغة

العمل المختبري رقم 3

يعد تطوير محلل معجمي أمرًا بسيطًا للغاية إذا تم استخدام نظرية اللغات العادية والأتمتة المحدودة. في إطار هذه النظرية، تعتبر فئات المعاجم من نفس النوع لغات رسمية (لغة المعرفات، لغة الثوابت، وما إلى ذلك)، والتي يتم وصف مجموعة الجمل منها باستخدام القواعد التوليدية المقابلة. علاوة على ذلك، فإن هذه اللغات بسيطة للغاية بحيث يتم إنشاؤها بواسطة أبسط قواعد النحو - القواعد النحوية العادية.

التعريف 1. القواعد التوليدية G = ، قواعدها لها الشكل: A::=aB أو C::=b، حيث A، B، CЄ N؛ a، b Є Т يسمى عادي (تلقائي).

تسمى اللغة L (G) التي تم إنشاؤها بواسطة القواعد النحوية الآلية لغة آلية (عادية) أو لغة ذات عدد محدود من الحالات.

مثال 1. فئة من المعرفات، إذا كان المعرف عبارة عن تسلسل يتكون من أحرف وأرقام، ويمكن أن يكون الحرف الأول من المعرف حرفًا فقط، يتم وصفه بالقواعد التوليدية المنتظمة التالية G = ، حيث

ن = (أنا، ك)، تي = (ب، ج)، ق = (أنا)،

ف = (1. أنا::= ب

هنا b، c عبارة عن رموز طرفية عامة لتعيين الحروف والأرقام، على التوالي.

يتم وصف عملية إنشاء المعرف "bbcbc" بالتسلسل التالي من البدائل

أنا => بي بي سي => بي بي سي => بي بي سي => بي بي سي => بي بي سي

ومع ذلك، فإن المهمة الرئيسية لـ LA ليست توليد الوحدات المعجمية، ولكن التعرف عليها. النموذج الرياضي لعملية التعرف على اللغة العادية هو جهاز حاسوبي يسمى آلة الحالة المحدودة (FA). يؤكد المصطلح "محدود" على أن جهاز الكمبيوتر يحتوي على كمية ثابتة ومحدودة من الذاكرة ويعالج سلسلة من رموز الإدخال التي تنتمي إلى مجموعة محدودة. هناك أنواع مختلفة من KA، إذا كانت وظيفة الإخراج KA (نتيجة العمل) هي مجرد إشارة إلى ما إذا كان تسلسل إدخال الرموز مقبولًا أم لا، يسمى هذا KA الحل النهائي.

التعريف 2. الخمسة التالية تسمى إنسانًا محدودًا:

أ = ، حيث V = (a 1 , a 2 , …, a m ) - أبجدية الإدخال (مجموعة محدودة من الرموز) ؛

Q = (q 0 , q 1 , …, q n -1 ) – أبجدية الحالات (مجموعة محدودة من الرموز);

δ: Q ×V →Q – وظيفة الانتقال؛

ف 0 Є س – الحالة الأولية للآلة المحدودة؛

FЄ Q – مجموعة الحالات النهائية.

مخطط تشغيل المركبة الفضائية.

يوجد شريط لا نهائي، مقسم إلى خلايا، كل منها يمكن أن تحتوي على رمز واحد من V. السلسلة α Є V* مكتوبة على الشريط. الخلايا الموجودة على يسار ويمين السلسلة فارغة. يوجد جهاز تحكم نهائي (FCU) مزود برأس قراءة يمكنه قراءة الأحرف من الشريط بشكل تسلسلي، ويتحرك على طول الشريط من اليسار إلى اليمين. في هذه الحالة، يمكن أن تكون وحدة التحكم في أي حالة واحدة من Q. تبدأ وحدة التحكم عملها دائمًا في الحالة الأولية q 0، وتنتهي في إحدى الحالات النهائية F. في كل مرة، تنتقل إلى خلية جديدة على الشريط، تنتقل وحدة التحكم إلى حالة جديدة وفقًا للوظيفة δ.

يمكن تمثيل وظيفة انتقال المركبة الفضائية بالطرق التالية:

· مجموعة من الفرق.

· الرسم التخطيطي للدولة؛

· الجدول الانتقالي.

يتم كتابة أمر آلة الحالة على النحو التالي:

(q i، a j) → q k، حيث q i، q k Є Q؛ ي Є V.

يعني هذا الأمر أن آلة الحالة في الحالة q i، وتقرأ الرمز a j من الشريط وتنتقل إلى الحالة q k.

بيانياً، يتم تمثيل الأمر على شكل قوس بياني يمتد من قمة الرأس q i إلى قمة الرأس q k ويتم تمييزه بالرمز a j من أبجدية الإدخال:

يسمى التمثيل الرسومي للرسم بأكمله δ بمخطط الحالة لآلة الحالة المحدودة.

إذا وجدت المركبة الفضائية نفسها في موقف (q i، a j)، وهو ليس الجانب الأيسر من أي أمر، فإنها تتوقف. إذا قامت وحدة التحكم بحساب جميع رموز السلسلة α المسجلة على الشريط، وفي نفس الوقت تنتقل إلى الحالة النهائية q rЄ F، فإنهم يقولون إن السلسلة α مسموح بها بواسطة آلة الحالة المحدودة.

يتم إنشاء جدول انتقال المركبة الفضائية على النحو التالي: تتوافق أعمدة المصفوفة مع رموز من أبجدية الإدخال، وتتوافق الصفوف مع رموز من أبجدية الحالة، وتتوافق عناصر المصفوفة مع الحالات التي تنتقل إليها المركبة الفضائية لمجموعة معينة من رموز الإدخال ورمز الدولة.

دع القواعد النحوية العادية G = ، قواعدها لها الشكل: A i::= a j A k أو A i::= a j، حيث A i وA k Є N وa j Є T.

ثم الإنسان المحدود A = ، مع الاعتراف بنفس اللغة التي تولدها القواعد النحوية العادية G، يتم إنشاؤها على النحو التالي:

2) Q = N U (Z)، Z N و Z T، Z هي الحالة النهائية للمركبة الفضائية؛

5) تم إنشاء التعيين δ بالشكل:

· كل قاعدة استبدال في القواعد النحوية G للنموذج A i::= a j A k مرتبطة بالأمر (A i, a j) → A k;

· كل قاعدة استبدال من النموذج A i::= a j مرتبطة بالأمر (A i, a j) → Z;

مثال 2.أنشئ مرجعًا مصدقًا (CA) للقواعد النحوية من المثال 1. لدينا A = ، أين

1) الخامس = تي = (ب، ج)

2) س = N U (Z) = (I، R، Z)

3) ف 0 = (س) = (أنا)

5) δ: أ) على شكل مجموعة من الأوامر:

ب) في شكل مخطط الحالة

هناك آلات حالة محدودة حتمية وغير حتمية. تسمى المركبة الفضائية غير حتمية KA (NKA) ، إذا كانت عدة أقواس ذات علامات متطابقة تنبثق من قمة واحدة في مخطط حالتها. على سبيل المثال، KA من المثال 2 هو NKA.

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

Z - "السماح بسلسلة الإدخال"؛

O - "تم تذكر خطأ في سلسلة الإدخال"؛

هـ - "رفض سلسلة الإدخال".

الحالتان Z وE نهائيتان، وتنتقل إليهما المركبة الفضائية عند قراءة علامة النهاية ├، على التوالي، بعد معالجة سلسلة إدخال صحيحة أو خاطئة. الحالة O هي حالة متوسطة، تنتقل المركبة الفضائية إليها من أي حالة صالحة للمركبة الفضائية عند اكتشاف خطأ في سلسلة الإدخال وتبقى هناك حتى وصول علامة النهاية ├، وبعد ذلك تنتقل إلى الحالة E - "رفض سلسلة الإدخال". "

دع L 1 و L 2 هما لغتان في الأبجدية

ثم أي. تسلسل اللغةيتكون من تسلسل جميع كلمات اللغة الأولى مع جميع كلمات اللغة الثانية. على وجه الخصوص، إذا، ثم، وإذا، ثم.

دعونا نقدم تدوينًا لـ "درجات" اللغة L:

وبالتالي، L i يشمل جميع الكلمات التي يمكن تقسيمها إلى كلمات متتالية من L .

التكرار (L)* للغة L يتكون من جميع الكلمات التي يمكن تقسيمها إلى عدة كلمات متتالية من L:

ويمكن تمثيلها باستخدام الدرجات:

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

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

ويقدم الجدول التالي تعريفا استقرائيا رسميا التعبيرات العاديةعلى الأبجدية واللغات التي تمثلها.

التعبير ص	اللغة لام ص
	ل ل =(أ)
دع r 1 و r 2 يكونان	L r1 و L r2 -ممثل
التعبيرات العادية.	لهم اللغات.
ثم التعبيرات التالية
منتظمة	وتمثيل اللغات:
ص=(ص 1 + ص 2)
ص = (ص 1 دائرة 2)
ص=(ص 1) *	ل ص = ل ر1 ​​*

عند التسجيل التعبيرات العاديةسنحذف علامة التسلسل ونفترض أن العملية * لها أولوية أعلى من التسلسل و+، وأن التسلسل له أولوية أعلى من +. سيسمح هذا بحذف العديد من الأقواس. على سبيل المثال، يمكن كتابتها كـ 10(1 * + 0) .

التعريف 5.1. اثنين التعبيرات العاديةيقال أن r وp متكافئان إذا كانت اللغات التي يمثلونها هي نفسها، أي. ل ص = ل ص . في هذه الحالة نكتب r = p.

من السهل التحقق، على سبيل المثال، مما يلي خصائص العاديةعمليات:

• ص + ص= ص+ ص (إبدالية الاتحاد)،
• (r+p) +q = r + (p+q) (ترابط الاتحاد)،
• (ص ع) ف = ص (ف ف) (ترابط التسلسل)،
• (ص *) * = ص * (عجز التكرار)،
• (ص +ع) ف = ر ف + pq(التوزيعية).

مثال 5.1. لنثبت، على سبيل المثال، مساواة غير واضحة: (r + p) * = (r * p *) *.

لتكن L 1 هي اللغة الممثلة في جانبها الأيسر، وL 2 في جانبها الأيمن. الكلمة الفارغة تنتمي إلى كلتا اللغتين. إذا كانت الكلمة غير فارغة، فمن خلال تعريف التكرار يمكن تمثيلها على أنها سلسلة من الكلمات الفرعية التي تنتمي إلى اللغة. لكن هذه اللغة هي مجموعة فرعية من اللغة L"=L r * L p * (لماذا؟). لذلك . على العكس من ذلك، إذا كانت الكلمة، فيمكن تمثيلها كسلسلة من الكلمات الفرعية التي تنتمي إلى اللغة L". كل كلمة من هذه الكلمات الفرعية v يمكن تمثيلها في النموذج v= v 1 1 ... v k 1 v 1 2 ... v l 2، حيث بالنسبة للجميع i=1، ... ، k هي كلمة فرعية وبالنسبة للجميع j=1، ... ، l هي كلمة فرعية (من الممكن أن تكون k أو l تساوي 0). ولكن هذا يعني أن w عبارة عن سلسلة من الكلمات الفرعية، كل منها ينتمي إلى، وبالتالي، .

لغة عادية

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

تعريف المجموعة المنتظمة

دع Σ تكون أبجدية محدودة. مجموعة عاديةيتم تعريف R(Σ) في الأبجدية Σ بالخصائص العودية التالية:

أنظر أيضا

• بناء محلل على أساس نهج الأتمتة

مؤسسة ويكيميديا. 2010.

تعرف على ما هي "اللغة العادية" في القواميس الأخرى:

لغة عادية- - موضوعات الاتصالات، المفاهيم الأساسية باللغة العادية... دليل المترجم الفني

- (ريجولاريوس باللاتينية، من قاعدة ريجولا). صحيح، مرتبة بشكل صحيح، مصنوعة. التشغيل المنتظم للآلة. حتى السكتة الدماغية. الحياة العادية. حياة صحيحة وكريمة ورتيبة. قاموس الكلمات الأجنبية المدرجة في اللغة الروسية.... قاموس الكلمات الأجنبية للغة الروسية

سم … قاموس المرادفات

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

هذا المصطلح له معاني أخرى، انظر الكيشوا. الكيشوا الاسم الذاتي: Qhichwa Simi، Runa Simi البلدان ... ويكيبيديا

إطار مبنى به شبكة من الأعمدة أو الأعمدة مبنية على درجة من نفس الحجم (البلغارية؛ Български) هيكل عظمي موحد (التشيكية؛ Čeština) pravidelný skelet (ألمانية؛ ألمانية) regelmäßiges Skelett (المجرية؛ المجرية) szabályos... ... قاموس البناء

- [الحديقة الفرنسية] حديقة ذات تخطيط هندسي منتظم، عادةً ما يكون تخطيطًا محوريًا (البلغارية؛ Български) حديقة فرينسكي (تشيكية؛ Čeština) حديقة فرانكوزسكي (ألمانية؛ ألمانية) حديقة ريجيلماسيجر؛ حديقة فرانتسوسيشر…… قاموس البناء

الكيشوا الاسم الذاتي: Qhichwa Simi، Runa Simi البلدان: الأرجنتين، بوليفيا، كولومبيا، بيرو، تشيلي، الإكوادور المناطق: جبال الأنديز الوضع الرسمي: بيرو ... ويكيبيديا

لغة التاغالوغية- (تجال، تاجالا، تاجالو؛ تاجالوج) إحدى اللغات الفلبينية. تقع منطقة التوزيع الأولي في المنطقة الأكثر أهمية سياسياً واقتصادياً وثقافياً في جمهورية الفلبين - الأجزاء الوسطى والجنوبية من الجزيرة... ... القاموس الموسوعي اللغوي

كتب

• الأفعال المشتقة. أسرار قواعد اللغة الفنلندية. كتاب مدرسي، Safronov V.D.. الدليل مخصص لواحد من أكثر أقسام القواعد الفنلندية إثارة للاهتمام وغير المقدمة بشكل كافٍ في الأدب التعليمي باللغة الروسية - الأفعال المشتقة. وهي مكونة من أفعال ومن أسماء..