أتمتة محدودة قطعية

في نظرية الاتمتة و نظرية التشغيل الذاتي, فرع من فروع علم الحاسوب, الاتمتة المحدودة القطعية Deterministic Finite Automaton أو DFA اختصاراً أي الآلة المحدودة المدخلات وقطعية أو معروفة المخرجات الآلة ذاتية التشغيل (محددة), هي آلة تقوم بقبول أو رفض الحروف أو الرموز وتنتج عملية حسابية معينة عند عملها أو عند ادخال الحروف أو الرموز عليها, قدم ابسط صورها العالمان McCulloch و Pitts في عام 1943.

مثال على الاتمتة المحدودة القطعية مكونة من ثلاث حالات وتقبل الاعداد الثنائية حيث أن الحالة S₀ هي حالة البداية والنهاية القبول.

الصورة على اليمين هو تمثيل لـ آلة محدودة قطعية باستخدام النماذج الرياضية. في هذه الآلة هناك ثلاث حالات : S0, S1 و S2 (حيث كل دائرة تدل على حالة). هذه الآلة تقبل عدد محدود من ال 0 والـ 1 كمدخلات. في كل حالة من الثلاث حالات هناك سهم انتقال من حاله إلى أخرى. في حالة قرائة رمز أو حرف معين 0 و 1 في هذه الحالة الآلة تنتقل من حالة إلى أخرى بشكل قطعي ومحدد.

الـ DFA معرفة كـ النماذج الرياضية, لكن بسبب طبيعتها القطعية, هي مطبقة في البرمجيات والـعتاد الحاسوب لحل العديد من المشاكل المحددة.[1][2][3] على سبيل المثال : نموذج رياضي يمثل DFA يطبق كبرمجية تقوم بتقرير ما ان كان أحد المستخدمين على الشبكة ام لا أو تدقيق بريده الإلكتروني على سبيل المثال.

التعريف

الـالاتمتة المحدودة القطعية مكونة من M is a 5-عناصر (Q, Σ, δ, q₀, F)

عدد محدود من الحالات (Q)
عدد محدود من رموز المدخلات لغة (Σ)
عملية نقل اقتران (δ : Q × Σ → Q)
a حالة البداية (q₀ ∈ Q)
مجموعة من حالات القبول (F ⊆ Q)

مراجع

Cai, X.S.; Devroye, L. "The graph structure of a deterministic automaton chosen at random: full version". arXiv:1504.06238. الوسيط |CitationClass= تم تجاهله (مساعدة)
Grusho, A. A. (1973). "Limit distributions of certain characteristics of random automaton graphs". Mathematical Notes of the Academy of Sciences of the USSR. 4: 633–637. doi:10.1007/BF01095785. الوسيط |CitationClass= تم تجاهله (مساعدة)
Carayol, Arnaud; Nicaud,, Cyril (2012). "Distribution of the number of accessible states in a random deterministic automaton". مؤرشف من الأصل في 09 أغسطس 2016. الوسيط |CitationClass= تم تجاهله (مساعدة); Cite journal requires |journal= (مساعدة)CS1 maint: extra punctuation (link)

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Cai, X.S.; Devroye, L. "The graph structure of a deterministic automaton chosen at random: full version". arXiv:1504.06238. الوسيط |CitationClass= تم تجاهله (مساعدة)

[2] Grusho, A. A. (1973). "Limit distributions of certain characteristics of random automaton graphs". Mathematical Notes of the Academy of Sciences of the USSR. 4: 633–637. doi:10.1007/BF01095785. الوسيط |CitationClass= تم تجاهله (مساعدة)

[3] Carayol, Arnaud; Nicaud,, Cyril (2012). "Distribution of the number of accessible states in a random deterministic automaton". مؤرشف من الأصل في 09 أغسطس 2016. الوسيط |CitationClass= تم تجاهله (مساعدة); Cite journal requires |journal= (مساعدة)CS1 maint: extra punctuation (link)