با توجه به قضیه کلین، هر عبارت منظم را می توان با یک خودکار متناهی مرتبط کرد، که یک مدل رسمی از الگوریتم برای تشخیص واژگان مشخص شده با این عبارت منظم است. در کلی‌ترین عبارت، یک تشخیص‌دهنده خودکار محدود با مجموعه محدودی از حالت‌های جریان ورودی مشخصه آن و انتقال بین آنها تعریف می‌شود. هنگامی که کاراکترهای جریان ورودی را از یک الفبای معین مطابق با تابع انتقال دریافت می‌کنید، تغییر حالت رخ می‌دهد، که حالت‌های بعدی احتمالی را از کاراکتر ورودی و وضعیت فعلی تعیین می‌کند. در میان حالت‌های ممکن، حالت‌های اولیه (اولیه) و نهایی (مجاز) مشخص می‌شوند که در آن تشخیص‌دهنده ماشین وضعیت می‌تواند به ترتیب در شروع و تکمیل پردازش نشانه‌های جریان ورودی باشد. اگر دنباله نویسه‌های ورودی بتواند دنباله‌ای از انتقال ایجاد کند که بتواند خودکار محدود را از حالت اولیه به یکی از حالت‌های نهایی منتقل کند، آنگاه به عنوان پذیرنده در نظر گرفته می‌شود و متعلق به مجموعه منظمی است که تشخیص می‌دهد.

(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*

میز 1

تحلیل واژگانی. زبان‌های معمولی و خودکارهای محدود

با تعداد کل کاراکترهای حروف الفبای نمادها و علائم عملیات و براکت ها در رکورد r.

اساس. اتومات برای عبارات طول 1: و در شکل زیر نشان داده شده است.

برنج. 5.1.

توجه داشته باشید که هر یک از این سه خودکار دارای مجموعه ای از حالات نهاییاز یک دولت تشکیل شده است.

مرحله القاء. اکنون برای هر کدام فرض کنیم عبارت منظمطول<= k построен соответствующий НКА, причем у него единственное заключительное состояние. Рассмотрим произвольное عبارت منظم r به طول k+1 . بسته به آخرین عملیات، می تواند یکی از سه شکل را داشته باشد: (r 1 + r 2)، (r 1 r 2) یا (r 1) * . اجازه دهید و NFA هایی باشند که به ترتیب زبان های L r1 و L r2 را تشخیص می دهند. بدون از دست دادن کلیت، فرض می کنیم که آنها حالت های مختلفی دارند: .

سپس NFA که نمودار آن در شکل نشان داده شده است. 5.2، زبان را می شناسد.

برنج. 5.2.

این دستگاه دارد مجموعه ایالت ها، که در آن q 0 یک حالت اولیه جدید است، q f یک حالت نهایی جدید (بی نظیر!) است و این برنامه شامل برنامه های خودکار M 1 و M 2 و چهار دستور انتقال جدید است: . بدیهی است که زبان شناسایی شده توسط NFA M شامل همه کلمات از L (M 1) و از L (M 2) است. از طرف دیگر، هر کلمه q 0 تا q f را می گیرد و پس از اولین قدم مسیر حامل آن از q 0 1 یا q 0 2 می گذرد. از آنجایی که حالت‌های M 1 و M 2 قطع نمی‌شوند، در حالت اول این مسیر می‌تواند به q f برسد فقط با انتقال -از q f 1 و سپس . به همین ترتیب، در مورد دوم.

برای بیان، نمودار NFA که زبان L r را تشخیص می دهد در شکل زیر نشان داده شده است.

برنج. 5.3.

این دستگاه دارد مجموعه ایالت ها , حالت اولیه q 0 = q 0 1 , حالت نهایی q f =q f 2 , و برنامه شامل برنامه های خودکار M 1 و M 2 و یک دستورالعمل جدید - انتقال از حالت نهایی M 1 به حالت اولیه M 2 , i.e. . در اینجا نیز بدیهی است که هر مسیری از q 0 = q 0 1 به q f = q f 2 از یک - گذار از q f 1 به q 0 2 می گذرد. بنابراین هر کلمه ای که م مجاز بداند، الحاق کلمه ای از L M1 ) با کلمه ای از L M2 ) است و هر گونه الحاق چنین کلماتی مجاز است. بنابراین، NFA M زبان را تشخیص می دهد.

اجازه دهید r = r 1 * . نمودار NFA که زبان را تشخیص می دهد L r = L r1 * = L M1 * در شکل نشان داده شده است. 5.3.

برنج. 5.3.

این دستگاه دارد مجموعه ایالت ها، که در آن q 0 یک حالت اولیه جدید است، q f یک حالت نهایی جدید (بی نظیر!) است و این برنامه شامل برنامه خودکار M 1 و چهار دستور انتقال جدید است: . به طور مشخص، . برای یک کلمه غیر خالی w، با تعریف تکرار برای برخی از k >= 1 کلمه w را می توان به k زیرکلمه تقسیم کرد: w=w 1 w 2 ... w k و بس. برای هر i= 1,... ,k کلمه w i q 0 1 را به q f 1 نشان می دهد. سپس برای کلمه w در نمودار M یک مسیر وجود دارد

در نتیجه، . برعکس، اگر کلمه‌ای q 0 را به q f ترجمه کند، یا وجود دارد یا توسط مسیر q 0 1 توسط -transition حمل می‌شود، در نهایت از q f 1 توسط -transition به q f ختم می‌شود. بنابراین، چنین کلمه ای.

از قضایای 4.2 و 5.1 مستقیماً به دست می آوریم

نتیجه 5.1. برای همه عبارت منظممی توان به طور مؤثر یک خودکار متناهی قطعی ساخت که زبان نشان داده شده توسط این عبارت را تشخیص دهد.

این بیانیه یک نمونه است قضایای سنتز: با توجه به شرح کار (زبان به عنوان عبارت منظم) یک برنامه (DFA) که آن را اجرا می کند به طور موثر ساخته شده است. عکس آن نیز صادق است - قضیه تحلیل.

قضیه 5.2. برای هر خودکار محدود قطعی (یا غیر قطعی) می توان ساخت عبارت منظم، که نشان دهنده زبان شناخته شده توسط این خودکار است.

اثبات این قضیه کاملاً فنی است و خارج از محدوده درس ما است.

بنابراین، می‌توان نتیجه گرفت که کلاس زبان‌های خودکار محدود با کلاس منطبق است زبان های معمولی. در ادامه، ما به سادگی آن را نام خواهیم برد کلاس زبان های خودکار.

خودکار Mr که در اثبات قضیه 5.1 ساخته شده است

تعاریف اساسی عبارات با قاعده در الفبای Σ و مجموعه های منظمی که آنها را نشان می دهند به صورت بازگشتی به صورت زیر تعریف می شوند: 1) یک عبارت منظم که یک مجموعه منظم را نشان می دهد. 2) e یک عبارت منظم است که یک مجموعه منظم را نشان می دهد (e). 3) اگر Σ، a یک عبارت منظم است که مجموعه منظم (a) را نشان می دهد. 4) اگر p و q عبارت‌های منظمی هستند که مجموعه‌های منظم P و Q را نشان می‌دهند، a) (p+q) یک عبارت منظم است که نشان‌دهنده PQ است. ب) pq یک عبارت منظم است که PQ را نشان می دهد. ج) p* یک عبارت منظم است که P* را نشان می دهد. 5) هیچ چیز دیگری یک عبارت منظم نیست.

تعاریف اساسی اولویت بندی: * (تکرار) – بالاترین اولویت. الحاق + (اتحادیه). بنابراین 0 + 10* = (0 + (1 (0*))). مثال: 1. 01 به معنی (01); 2. 0* - (0*); 3. (0+1)* - (0, 1)*; 4. (0+1)* 011 - به معنی مجموعه تمام رشته هایی است که از 0 و 1 تشکیل شده و به رشته 011 ختم می شود. 5. (a+b) (a+b+0+1)* به معنی مجموعه تمام رشته ها (0، 1، a، b)* است که با a یا b شروع می شود.

تعاریف اصلی لم: 1) α + β = β + α 2) * = e 3) α + (β + γ) = (α + β) + γ 4) α (βγ) = (αβ)γ 5 ) α( β + γ) = αβ + αγ 6) (α + β)γ = αγ + βγ 7) αe = eα = α 8) α = 9) α+α* = α* 10) (α*)* = α* 11) α+α = α 12) α+ = α

ارتباطات RT و RM RM زبان هایی هستند که توسط RT تولید می شوند. به عنوان مثال: x = a+b، y = c+d، x X = (a، b)، y Y = (c، d)، x + y X Y = (a، b، c، d). الحاق: xy XY = (ac, ad, bc, bd). k(u+o)t (k)(u, o)(t) = (نهنگ، گربه) یا توسط لمای شماره 5 و شماره 6 k(u+o)m = نهنگ + گربه (نهنگ، گربه) . تکرار: x = a، x* X* = (e، a، aaa، ...)، یعنی x* = e + xxx + …

رابطه RT و RM تکرار الحاق و اتحاد: (xy)* = e + xyxyxy + ... (x + y)* = e + (x + y) (x + y) + ... = = e + xx + xy + yx + yy + xxx + … مثال: 0 + 1(0+1)* (0) ((1) (0, 1)*) = (0, 1, 10, 11, 100, 101, 110، 111…). اتحاد جابجایی است: x + y = y + x الحاق نیست: xy ≠ yx

رابطه بین RT و PM نمونه های اولویت: x + yz (x, yz), (x + y)z (xz, yz), x + y* (e, x, y, yyy, yyyy, …) (x + y)* (e، x، y، xx، xy، yx، yy، xxx، …)، (xy)* (e، xyxy، …)، xy* (x، xyy، xyyy، …). لم های جدید: a* + e = a*; (a + e)* = a*; a*a* = a*; e* = e; و غیره.

سیستم های منتظم معادلات معادله با ضرایب منظم X = a. X + b یک راه حل دارد (کوچکترین نقطه ثابت) a*b: aa*b + b = (aa* + e)b = a*b سیستم معادلات با ضرایب منظم: X 1 = α 10 + α 11 X 1 + α 12 X 2 + … + α 1 n. Xn X 2 \u003d α 20 + α 21 X 1 + α 22 X 2 + ... + α 2 n. Xn…………………………. . Xn = αn 0 + αn 1 X 1 + αn 2 X 2 + … + αnn. Xn ناشناخته - Δ = (X 1، X 2، ...، Xn).

سیستم های منظم معادلات الگوریتم حل (روش گاوس): مرحله 1. i = 1. مرحله 2. اگر i = n به مرحله 4 بروید. در غیر این صورت، معادلات Xi را به صورت Xi = αXi + β بنویسید (β = β 0 + βi +1 Xi+1 + … + βn.Xn). سپس، در سمت راست معادلات Xi+1، …، Xn، عبارت منظم α*β را جایگزین Xi می کنیم. مرحله 3. i را 1 افزایش دهید و به مرحله 2 برگردید. مرحله 4. معادله Xn را به صورت Xn = αXn + β بنویسید. به مرحله 5 بروید (با i = n). مرحله 5. معادله Xi Xi = αXi + β است. در خروجی Xi = α*β بنویسید، در معادلات Xi– 1، …، X 1 به جای Xi، α*β را جایگزین کنید. مرحله 6. اگر i = 1 است، توقف کنید، در غیر این صورت i را 1 کاهش دهید و به مرحله 5 برگردید.

تبدیل DFA به RW برای DFA M = (Q, Σ, δ, q 0, F) ما سیستمی با ضرایب منظم می سازیم که در آن Δ = Q: 1. αij: = ; 2. اگر δ(Xi، a) = Xj، a Σ، آنگاه αij: = αij + a; 3. اگر Xi F یا δ(Xi،) = HALT، آنگاه αi 0: = e. پس از حل RV مورد نظر X 1 = q 0 خواهد بود.

تبدیل DFA به RW مثال: برای یک عدد نقطه ثابت، سیستم q 0 = + q 0 + sq 1 + pq 2 + dq 3 + q 4 q 1 = + q 0 + q 1 + pq 2 + dq 3 به دست می آید. + q 4 q 2 = + q 0 + q 1 + q 2 + q 3 + dq 4 q 3 = e + q 0 + q 1 + q 2 + dq 3 + pq 4 = e + q 0 + q 1 + q 2 + q 3 + dq 4 در اینجا: s علامت عدد است، s = "+" + "-"; p – نقطه اعشار، p = "."; d - اعداد، d = "0" + "1" + ... + "9".

راه حل تبدیل DFA به RW: q 0 = * (sq 1 + pq 2 + dq 3 + q 4 +) = sq 1 + pq 2 + dq 3 q 1 = + q 0 + q 1 + pq 2 + dq 3 + q 4 = pq 2 + dq 3، q 2 = + q 0 + q 1 + q 2 + q 3 + dq 4 = dq 4، q 3 = e + q 0 + q 1 + q 2 + dq 3 + pq 4 = dq 3 + pq 4 + e، q 4 = e + q 0 + q 1 + q 2 + q 3 + dq 4 = dq 4 + e. از معادله سوم: q 3 \u003d dq 3 + pq 4 + e \u003d d * (pq 4 + e). از معادله چهارم: q 4 = dq 4 + e = d *.

تبدیل DFA به RW معکوس: q 3 = d*(pq 4 + e) = d*(pd* + e)، q 2 = dq 4 = dd*، q 1 = pq 2 + dq 3 = pdd* + dd *(pd* + e)، q 0 = sq 1 + pq 2 + dq 3 = s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e). بنابراین، این DFA با RE s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e) مطابقت دارد. برای ساده کردن: s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e) = = spdd* + sdd*(pd* + e) + pdd* + dd*(pd* + e) = (s + e)(pdd* + dd*(pd* + e)) برای نماد کوتاه تر، می توانید از تکرار مثبت aa* = a*a = a+ استفاده کنید: (s + e) )(pdd* + dd* (pd* + e)) = (s + e)(pd+ + d+pd* + d+)

تبدیل DFA به RT نگاشت نمودار تابع انتقال DFA به عملیات بیان منظم پایه: q 0 a b a q 1 q 2 q 1 q 0 a+b a b ab q 2 a*

تبدیل DFA به RT ترکیبات پیچیده تر از عملیات: q 0 a q 1 b b b q 0 a q 2 q 1 (a + e)b c b q 0 q 2 ab(cab)* q 0 (a + b)* q 0 a q 1 aa* = a+ q 0 a q 1 a b a a (ab)+ q 2 b q 1 c e + (a + b)c*

تبدیل DFA به RW برای RW (s + e) (pd+ + d+(pd* + e)): q 0 p q 2 d s p q 1 d d q 3 d p q 4 d q 5 d

عبارات منظم برنامه نویسی زمان واقعی: ساخته شده در بسیاری از زبان های برنامه نویسی (PHP، جاوا. اسکریپت، ...)؛ به عنوان پلاگین پیاده سازی شده است (به عنوان مثال، کلاس Regex برای پلت فرم دات نت). تفاوت در اشکال نوشتاری: x؟ = x + e x(1، 3) = x + xxx و غیره.

برنامه نویسی RT ساختارهای کلاس Regex (System.Text.Regular.Expressions): تعبیر دنباله فرار کاراکتر b هنگامی که در کروشه استفاده می شود، با کاراکتر "←" (u 0008) t, r, n, a, f, v Tab (u) مطابقت دارد 0009)، بازگشت کالسکه (u 000 D)، خط جدید (u 000 A)، و غیره ج. X کاراکتر کنترل (مثلاً c. C Ctrl+C، u 0003 است) e Escape (u 001 B) ooo نویسه ASCII Octal xhh نویسه ASCII Hex uhhhh کاراکتر Unicode کاراکتر زیر یک کاراکتر PB خاص نیست. تمام کاراکترهای خاص باید با این کاراکتر حذف شوند. مثال (در مثال، الگو و رشته جستجو آورده شده است، مطابقت های یافت شده در رشته زیر خط کشیده شده اند): @"rnw+" – "rn. در اینجا n دو رشته وجود دارد" .

برنامه نویسی RT زیر مجموعه کاراکترها. هر کاراکتری به جز انتهای رشته (n) هر کاراکتری از مجموعه [^xxx] هر کاراکتری به جز کاراکترهای مجموعه هر کاراکتری از محدوده ] یک مجموعه یا محدوده را از p(name) دیگر کم کنید هر کاراکتری که توسط یونیکد مشخص شده است دسته با نام P (نام) هر کاراکتری غیر از نویسه‌های مشخص شده توسط دسته یونیکد با نام w مجموعه نویسه‌هایی که در تعیین شناسه‌ها استفاده نمی‌شوند W مجموعه نویسه‌هایی که در تعیین شناسه‌ها استفاده نمی‌شوند فضاهای S هر چیزی به جز فاصله‌ها d رقم‌ها D بدون رقم مثال‌ها: @ ". +" - "rn. در اینجا n دو خط وجود دارد"; @"+" - "0xabcfx"؛ @"[^fx]+" - "0 xabcfx"; @"+" - "0xabcfx"؛ @"[^a-f]+" - "0 xabcfx"; @"]+" - "0xabcfx"؛ @"p(Lu)" - "چراغ های شهر"؛ // Lu - حروف بزرگ @"P(Lu)" - "شهر"؛ @"p(Is. Cyrillic)" - "ha. OS"؛ // است. سیریلیک - حروف روسی

PB Programming Anchor ^, A در ابتدای رشته $, Z در انتهای رشته یا تا کاراکتر "n" در انتهای رشته z در انتهای رشته G جایی که مطابقت قبلی به پایان رسید b Word مرز B هر موقعیتی که روی مرز یک کلمه نباشد مثال‌ها: @ "G(d)" - "(1)(3)(5)(9)"; // سه مسابقه (1)، (2) و (3) @"bnS*ionb" – "اهدای ملت"؛ @"Bendw*b" - "پایان می فرستد استقامت وام دهنده".

برنامه نویسی عملیات RT (کمی سازها) *، *؟ تکرار +، +؟ تکرار مثبت؟ ، ? صفر یا یک مسابقه (n)، (n)؟ دقیقاً n منطبق با (n، )، (n، ) است؟ حداقل n مسابقه (n، m)، (n، m)؟ از n تا m منطبق است مثال‌ها (کمی‌شگرهای اول حریص هستند، به دنبال تا حد ممکن عناصر هستند، دومی‌ها تنبل هستند، به دنبال کمترین عنصر هستند): @"d(3, )" – "888 -5555"; @"^d(3)" - "913 -913"; @"-d(3)$" - "913 -913"; @"5+؟ 5" - "888 -5555"؛ // سه مسابقه - 55، 55 و 55 @"5+5" - "888 -5555".

گروه بندی برنامه نویسی RT () گروه به طور خودکار یک عدد اختصاص می دهد (?:) گروه (؟) یا (? "نام") را ذخیره نکنید اگر مطابقت یافت شد، یک گروه با نام ایجاد کنید (؟) یا یک گروه از قبل تعریف شده را حذف کنید و (؟ "name-name") در گروه جدید یک زیر رشته بین گروه تعریف شده قبلی و گروه جدید ذخیره می کند (? imnsx:) هر یک از پنج گزینه (? -imnsx:) را در گروه روشن یا خاموش می کند: i - case. غیر حساس s یک خط است (سپس ". " هر کاراکتری است). m - حالت چند خطی ("^" ، "$" - ابتدا و انتهای هر خط)؛ n - گروه های بی نام را دستگیر نکنید. x - فضاهای بدون گریز را از الگو حذف کنید و نظرات بعد از علامت عدد (#) (?=) ادعای پیش بینی مثبت با طول صفر را اضافه کنید.

برنامه نویسی RE (? !) ادعای پیش بینی منفی با طول صفر (؟) بخش بی بازگشت (حریصی) بیان مثال: @"(an)+" – "bananas annals"; @"an+" - "سالانه موز"؛ // مقایسه، سه مسابقه - an، an و ann @"(? i: an)+" - "ba. NAnas annals"; @"+(? =d)" - "abc xyz 12 555 w"; @"(؟

Src="https://website/presentation/-112203859_437213351/image-24.jpg" alt="(!LANG:Programming RT شماره مرجع مرجع گروه k مرجع گروه نامگذاری شده مثالها: @"> Программирование РВ Ссылки число Ссылка на группу k Ссылка на именованную группу Примеры: @"(w)1" – "deep"; @"(? w)k " – "deep". Конструкции изменения | Альтернатива (соответствует операции объединения) (? (выражение)да|нет) Сопоставляется с частью «да» , если выражение соответствует; в противном случае сопоставляется с необязательной частью «нет» (? (имя)да|нет), Сопоставляется с частью «да» , если названное имя (? (число)да|нет) захвата имеет соответствие; в противном случае сопоставляется с необязательной частью «нет» Пример: @"th(e|is|at)" – "this is the day";!}

جایگزین‌های برنامه‌نویسی RT $number قسمتی از رشته مربوط به گروه را با عدد مشخص شده جایگزین می‌کند $(name) قسمتی از رشته مربوط به گروه را با نام مشخص شده جایگزین می‌کند $$ جایگزین $$& جایگزینی با یک کپی از کامل مطابقت $` جایگزین متن رشته ورودی تا مطابقت شود $" جایگزینی متن خط ورودی بعد از مسابقه $+ جایگزینی آخرین گروه ثبت شده $_ جایگزینی کل خط نظرات (? #) نظر درون خطی # نظر تا انتهای خط

نتایج برنامه نویسی RT Regex: Regex Matches() Match. گروه تطبیق مجموعه () Collection Group Captures() Capture. مجموعه عکس‌ها()

مثال برنامه نویسی RT در C++ CLI (برنامه کنسول ویژوال C++/CLR/CLR): int main() ( Regex ^r = gcnew Regex(L"((\d)+)+"); Match ^m = r-> Match (L"123 456"); int match. Count = 0; while (m-> Success) (کنسول: : Write. Line(L"Match(0)", ++ match. Count); for (int i = 1؛ i Groups->Count; i++) (گروه ^g = m->Groups[i]؛ کنسول:: نوشتن. خط (L" گروه (0) = "(1)"، i، g-> مقدار برای (int j = 0; j Captures->Count; j++) (Capture ^c = g->Captures[j]؛ کنسول: : Write.Line(L" Capture(0) = "(1)" , موقعیت = (2)، طول = (3)"، j، c، c->Index، c->Length؛ ) ) m = m->Next. Match(); ) return 0; ) System: : متن : :منظم. اصطلاحات

گنجاندن اقدامات و جستجوی خطاها محدود کردن تعداد ارقام مهم در یک عدد: (s + e)(pd+ + d+(pd* + e)) s = +|p = . d = ds + e = s؟ = (+|-)؟ pd* + e = (pd*)؟ =(.d*)؟ @"(+|-)؟ (. d+|d+(. d*)?)" یا @"^(+|-)؟ (. d+|d+(. d*)?)$" Regex r = Regex جدید (@"^(+|-)؟ (. (? "رقم"d)+|(? "رقم"d)+(. (? "رقم"d)*)؟)$"); با m = r مطابقت دهید. مطابقت ("+1. 23456789"); if (m. موفقیت) (گروه g = m. گروه‌ها ["رقم"]؛ اگر (g. ضبط‌ها. تعداد

فعال کردن اقدامات و یافتن خطاها تعیین موقعیت یک خطا: Regex r = new Regex(@"(+|-)؟ (. (? "digit"d)+|(? "digit"d)+(. (? " رقم "d )*)؟)"); string str = "+1.2345!678"; با m = r مطابقت دهید. مسابقه (خ); if (m. موفقیت) (گروه g = m. گروه‌ها["رقم"]؛ if (g. عکس‌برداری. تعداد 0) کنسول. نوشتن. خط ("خطا در موقعیت 1: نویسه غیرمنتظره "(0)""، str )؛ در غیر این صورت (m.Length

فعال کردن اقدامات و جستجوی خطاها تعیین موقعیت خطا: 1. موقعیت اول رشته ورودی (1)، اگر اولین تطابق از موقعیت Index = 0 شروع نشود. 2. موقعیت بعد از آخرین تطابق (مطابقت. طول + 1)، اگر با آخرین موقعیت رشته ورودی مطابقت نداشته باشد. 3. موقعیت اولین استراحت بین مسابقات (مطابقت[i]. فهرست + تطابق[i]. طول + 1)، در صورتی که کاراکتر بعدی مسابقه قبلی اولین کاراکتر مسابقه بعدی نباشد.

index) break; شاخص = m[i]. شاخص + m[i]. طول؛ ) کنسول. نوشتن. خط ("خطا در موقعیت (0) "(1)""، فهرست + 1، str); ) "abc. xyz. pqr" صحیح است. + abc xyz. pqr" - خطا در موقعیت 1 ("+")؛ "abc. xyz. pqr!" - خطا در موقعیت 12 ("!")؛ "abc. xyz!. pqr" - خطا در موقعیت 8 ("!").

گنجاندن اقدامات و جستجوی خطاها اما! "abc. xyz. +pqr" - خطا در موقعیت 8 (." "). نوع الگوی جدید: @"w+(. w+)*(. (? !$))؟ " اعتبارسنجی: "abc. xyz. +pqr" - خطا در موقعیت 9 ("+")؛ "abc. xyz. pqr. "- یک خطا در موقعیت 12 (." ").

تعاریف متوازن: "(? "x")" یک عنصر به مجموعه به نام "x" اضافه می کند. "(? "-x")" یک عنصر را از مجموعه "x" حذف می کند. "(? (x)(? !))" بررسی می کند که هیچ عنصری در مجموعه "x" باقی نمانده باشد. زبان L که عبارات تودرتوی زبان پاسکال را توصیف می‌کند: «آغاز پایان; ': @"^s*((? "Begins+)+(? "-Begin"ends*; s*)+)*(? (Begin)(? !))$".

توصیف واژگان یک زبان در قالب عبارات منظم و تشخیص زبان با کمک KA راحت تر است. بنابراین، مهم است که بتوانیم تعاریف زبان را در قالب عبارات منظم به تعریفی در قالب FA تبدیل کنیم. چنین تحولی توسط کنت تامپسون پیشنهاد شد.

ماشین حالت پنج است (S، S، d، S 0، F)

S مجموعه ای محدود از حالات است.

S مجموعه محدودی از سیگنال های ورودی معتبر است.

د - تابع انتقال. مجموعه Sx(SÈ(e)) را در مجموعه حالت های یک خودکار متناهی غیر قطعی منعکس می کند. برای یک خودکار قطعی، تابع انتقال مجموعه SxS را به مجموعه حالت های خودکار منعکس می کند. به عبارت دیگر، بسته به حالت و نماد ورودی، d وضعیت جدید خودکار را تعیین می کند.

S 0 - حالت اولیه خودکار محدود، S 0 О S.

F مجموعه ای از حالت های نهایی خودکار، F О S است.

عملکرد یک ماشین حالت متوالی از مراحل است. مرحله با وضعیت خودکار و نماد ورودی تعیین می شود. خود مرحله شامل تغییر وضعیت خودکار و خواندن نماد بعدی دنباله ورودی است.

قوانین زیر برای تبدیل عبارات منظم به یک ماشین حالت وجود دارد.

1 عبارت منظم "e" به یک خودکار از دو حالت و یک انتقال الکترونیکی بین آنها تبدیل می شود (شکل 1).

شکل 1. - خودکار برای انتقال الکترونیکی

2 یک عبارت منظم از یک کاراکتر "a" به یک ماشین حالت محدود از دو حالت و یک انتقال بین آنها مطابق با سیگنال ورودی a تبدیل می شود (شکل 2).

شکل 2. - خودکار برای پرش با نماد a

3 بگذارید یک عبارت منظم rs و خودکارهای محدود برای عبارت r وجود داشته باشد و عبارت s قبلا ساخته شده است. سپس دو اتوماتا به صورت سری به هم متصل می شوند. شکل 3 خودکار اولیه برای زبان های r و s را نشان می دهد. شکل یک خودکار برای تشخیص الحاق این زبان ها را نشان می دهد.

خودکار برای r خودکار برای s

شکل 3. - اتوماتای اولیه

شکل 4. - ماشین الحاق زبانها

4 بگذارید یک عبارت منظم r | وجود داشته باشد s و اتوماتای محدود قبلاً برای عبارت r و عبارت s ساخته شده اند (شکل 3). سپس در خودکار حاصل باید جایگزینی برای اجرای یکی از دو خودکار وجود داشته باشد. یعنی خودکار برای عبارت r | s برای خودکار برای r و s از شکل 3 شکل نشان داده شده در شکل 5 را دارد.

شکل 5. - ماشینی برای ترکیب زبان ها

5 بگذارید یک عبارت منظم r* با خودکار محدود ساخته شده r وجود داشته باشد. در این حالت دو حالت جدید برای امکان دور زدن خودکار عبارت r و انتقال e- بین حالت نهایی و اولیه برای امکان تکرار چندگانه خودکار r معرفی می شود. اگر خودکاری مشابه شکل 3 برای عبارت منظم r ساخته شود، آنگاه خودکار متناهی نشان داده شده در شکل 6 با عبارت منظم r* مطابقت دارد.

	0	1
Q1	Q4	Q2
Q2	Q3	Q1
Q3	Q2	Q4
Q4	Q1	Q3

ستون‌های جدول انتقال، کاراکترهای الفبای ورودی را نشان می‌دهند و ردیف‌ها با حالت‌های فعلی DFA مطابقت دارند. عناصر هر خط نشان دهنده حالت های DFA است که هنگام دریافت کاراکترهای مربوط به الفبای ورودی باید از وضعیت فعلی تغییر کند. به طور خاص، از خط اول این جدول انتقال نتیجه می شود که دریافت نمادهای 0 و 1 در حالت اولیه Q1، DFA را به ترتیب به حالت های Q4 و Q2 منتقل می کند.

هنگام تشخیص دنباله ورودی از جدول انتقال، به راحتی می توان تغییرات حالت DFA را ردیابی کرد تا مشخص شود که آیا به یکی از حالت های پذیرنده رسیده است یا خیر. به طور خاص، برای یک بردار باینری 01001000 با تعداد زوج صفر و یک، DFA در نظر گرفته شده دنباله ای از انتقال را ایجاد می کند، که در آن هر انتقال با کاراکتر الفبای ورودی که آن را فراخوانی می کند برچسب گذاری می شود:

Q1 0 Q4 1 Q3 0 Q2 0 Q3 1 Q4 1 Q1 0 Q4 0 Q1

این دنباله از انتقال با حالت پذیرنده Q1 به پایان می رسد، بنابراین، بردار باینری 01001000 متعلق به مجموعه منظم شناخته شده توسط DFA در نظر گرفته شده است و عبارت منظم بالا را برآورده می کند.

در خاتمه لازم به ذکر است که روش غیررسمی ساخت

برای مطالعه بیشتر خواص اتوماتای محدود و به ویژه برای حل مسئله سنتز، قضیه زیر مهم است.

قضیه 7.7 (قضیه تعیین). برای هر خودکار متناهی، می توان یک خودکار متناهی قطعی معادل ساخت.

برای اثبات قضیه، ابتدا لازم است که الگوریتم ساخت یک خودکار محدود قطعی از نمونه اصلی را شرح دهیم. ثانیاً، این الگوریتم را با اثبات دقیق اینکه واقعاً یک خودکار متناهی را ارائه می دهد که قطعی و معادل نمونه اصلی است، توجیه کنید. در اینجا ما فقط الگوریتم ساخت یک خودکار قطعی را ارائه می دهیم.

تبدیل یک خودکار محدود دلخواه به یک خودکار قطعی معادل در دو مرحله انجام می شود: ابتدا قوس هایی با برچسب \lambda حذف می شوند، سپس تعیین واقعی انجام می شود.

1. حذف λ-transitions (قوس هایی با برچسب \lambda).

برای حرکت از ماشین حالت اصلی M=(V,Q,q_0,F,\delta)به خودکار متناهی معادل M"=(V،Q،q_0،F،\delta")بدون انتقال λ، انجام تبدیل های زیر در نمودار اصلی M کافی است.

آ. همه حالت ها، به جز حالت اولیه، که فقط با کمان هایی با برچسب \lambda وارد می شوند، حذف می شوند. این مجموعه Q" از خودکار متناهی M" را تعریف می کند. واضح است که Q"\subseteq Q . در این مورد، فرض می کنیم که حالت اولیه یکسان باقی می ماند.

ب مجموعه کمان های خودکار محدود M" و برچسب های آنها (بنابراین تابع انتقال M") به صورت زیر تعریف می شود: برای هر دو حالت p,r\in Q,~ p\to_(a)rاگر و فقط اگر a\in V وجود دارد، و یکی از موارد زیر در نمودار M برقرار است: یا یک کمان از p تا r وجود دارد که برچسب آن حاوی نماد a است، یا یک حالت q وجود دارد به طوری که p\Rightarrow_(\lambda)^(+)qو q\to_(a)r . در این مورد، راس q، به طور کلی، ممکن است به مجموعه Q تعلق نداشته باشد، یعنی ممکن است هنگام عبور به خودکار M ناپدید شود (شکل 7.11). اما اگر q\in Q"، طبیعتاً قوس (q,r) در M" حفظ می شود و نماد a یکی از نمادهای متعلق به برچسب این کمان خواهد بود (شکل 7.12).

بنابراین، در "M" همه کمان‌های M ذخیره می‌شوند که برچسب‌های آنها با \lambda متفاوت است و یک جفت (راس) حالت‌ها را از مجموعه Q به هم متصل می‌کنند (بر اساس مورد a حذف نشده است). علاوه بر این، برای هر سه حالت p,q,r (الزاماً متمایز نیست!)، به طوری که p,r\in Q" و مسیری با طول غیر صفر از p تا q وجود دارد که برچسب آن برابر با \lambda است. (یعنی مسیر توسط λ-transitions)، و از q به r یک قوس منتهی می شود که برچسب آن حاوی نماد a الفبای ورودی است، در M" یک کمان از p به r ساخته می شود که برچسب آن شامل نماد a (نگاه کنید به شکل 7.11).

که در. مجموعه حالت های نهایی F" خودکار متناهی M" شامل تمام حالات q\in Q" است، یعنی حالت های خودکار متناهی M که مطابق مورد a حذف نشده اند، که برای آن q\Rightarrow_(\lambda)^(\ast)q_fبرای برخی q_f\in F (یعنی یا خود حالت q حالت نهایی خودکار متناهی M است یا از آن مسیری با طول غیرصفر در امتداد کمان هایی با برچسب \lambda تا یکی از حالات نهایی متناهی وجود دارد. خودکار M ) (شکل 7.13).

2. در واقع عزم.

اجازه دهید M=(Q,V,q_0,F,\delta)یک خودکار متناهی بدون انتقال λ است. بیایید یک خودکار متناهی قطعی معادل M_1 بسازیم.

این خودکار محدود به گونه ای تعریف شده است که مجموعه حالت آن مجموعه ای از تمام زیر مجموعه های مجموعه حالت خودکار متناهی M است. این بدان معنی است که هر حالت جداگانه از خودکار محدود M_1 به عنوان زیر مجموعه ای از مجموعه حالت های خودکار محدود M تعریف می شود. در این مورد، حالت اولیه خودکار جدید متناهی (یعنی M_1) یک زیرمجموعه تک تنی است که شامل حالت اولیه خودکار محدود قدیمی (یعنی M) است، و حالات نهایی خودکار متناهی جدید همگی زیرمجموعه های Q هستند که شامل حداقل یک پایانی بالای خودکار متناهی اصلی M .

از این پس، با اجازه دادن مقداری آزادی بیان، ما گاهی اوقات حالت های خودکار محدود M_1 را حالت-مجموعه می نامیم. با این حال، مهم است که به وضوح درک کنیم که هر مجموعه حالتی یک حالت جداگانه از خودکار جدید محدود است، اما نه مجموعه ای از حالات آن. در عین حال، برای خودکار متناهی اصلی ("قدیمی") M، این دقیقاً مجموعه ای از حالات آن است. به بیان تصویری، هر زیر مجموعه ای از حالات خودکار متناهی قدیمی در یک حالت از خودکار متناهی جدید "جمع می شود"*.

*به طور رسمی، مجموعه Q_1 باید به عنوان مجموعه ای تعریف شود که با مجموعه 2^Q مطابقت یک به یک دارد، اما همچنان برای ما راحت تر است که در نظر بگیریم که Q_1 با 2^Q منطبق است، زیرا مجموعه از حالت های یک خودکار محدود می تواند هر مجموعه متناهی غیر خالی باشد.

تابع انتقال خودکار متناهی جدید به گونه‌ای تعریف می‌شود که از حالت S توسط نماد ورودی a، خودکار محدود M_1 به حالت مجموعه می‌رود که اتحادیه همه مجموعه‌های حالت‌های خودکار محدود قدیمی است. که این خودکار متناهی قدیمی با نماد a از هر مجموعه حالت S عبور می کند. بنابراین، خودکار متناهی M_1 با ساخت قطعی است.

شرح شفاهی فوق را می توان به فرمول هایی به صورت زیر ترجمه کرد: ما ماشین حالت M_1 را طوری می سازیم که

M_1=(Q_1،V،$q_0$،F_1،\delta_1)، جایی که

\begin(cases)Q_1=2^Q,\quad F_1=$T\colon\, T\cap F\ne\varnothing,~T\in2^Q$,\\ (\forall S\subseteq Q) (\forall a\in V)\Bigl(\delta_1(S,a)= \bigcup\limits_(q\in S)\delta(q,a)\Bigr). \پایان (موارد)

به این نکته توجه کنیم که در بین حالات خودکار متناهی جدید حالت \varnothing وجود دارد و طبق (7.8) \delta_1(\varnothing,a)=\varnothingبرای هر کاراکتر ورودی a . این بدان معنی است که وقتی در چنین حالتی قرار گیرد، ماشین حالت M_1 آن را ترک نخواهد کرد. به طور کلی، هر حالت q از یک خودکار متناهی به طوری که برای هر نماد ورودی a \delta(q,a)=q داشته باشیم، حالت جذب کننده خودکار متناهی نامیده می شود. بنابراین، حالت \varnothing ماشین حالت قطعی M_1 در حال جذب است. توجه به این نکته نیز مفید است \delta_1(S,a)=\varnothingاگر و فقط اگر برای هر q\in S (حالت های خودکار متناهی قدیمی از مجموعه حالت های S) \delta(q,a)=\varnothing، یعنی در نمودار M، هر حالت q هیچ کمانی با علامت a باقی نمی گذارد.

می توان ثابت کرد که خودکار متناهی به دست آمده توسط چنین الگوریتمی معادل نمونه اصلی است.

مثال 7.9.ما خودکار محدود نشان داده شده در شکل 1 را تعیین می کنیم. 7.14.

یک خودکار متناهی معادل بدون انتقال λ در شکل نشان داده شده است. 7.15. توجه داشته باشید که راس q_2 ناپدید می شود، زیرا فقط کمان های "خالی" وارد آن می شوند.

برای تعیین خودکار به دست آمده، مطلقاً لازم نیست که همه حالت های 2^3=8 آن را بنویسید، که بسیاری از آنها ممکن است از حالت اولیه $q_0$ قابل دسترسی نباشند. برای بدست آوردن حالت های قابل دسترسی از $q_0$ و فقط آنها، از روش به اصطلاح کشیدن استفاده می کنیم.

این روش را می توان در حالت کلی به شرح زیر توصیف کرد.

در خودکار متناهی اصلی (بدون قوس خالی)، ما تمام مجموعه حالت هایی را تعریف می کنیم که از حالت اولیه قابل دسترسی هستند، یعنی. برای هر کاراکتر ورودی a مجموعه \delta(q_0,a) را پیدا می کنیم. هر مجموعه ای از این قبیل در خودکار جدید حالتی است که مستقیماً از حالت اولیه قابل دسترسی است.

برای هر یک از مجموعه حالت های تعریف شده S و هر نماد ورودی a، مجموعه را پیدا می کنیم \textstyle(\mathop(\bigcup\limits_(q\in S) \delta(q,a))\limits^(\phantom(A)^(.))). تمام حالت‌های به‌دست‌آمده در این مرحله، حالت‌های یک خودکار جدید (قطعی) خواهند بود که از رأس اولیه در طول مسیری به طول 2 قابل دسترسی هستند. روش توصیف‌شده را تا زمانی که هیچ حالت-مجموعه جدیدی (از جمله حالت خالی) ظاهر نشود، تکرار می‌کنیم. می توان نشان داد که در این حالت تمام حالت های خودکار محدود M_1 به دست می آید که از حالت اولیه $q_0$ قابل دستیابی است.

برای ماشین حالت محدود در شکل. 7.15 داریم:

\begin(aligned)& \delta_1($q_0$,a)=$q_1$;\qquad \delta_1($q_0$,b)=$q_1,q_3$;\\ & \ delta_1($q_1$,a)=$q_1$;\qquad \delta_1($q_1$,b)=$q_1$;\\ & \delta_1($q_1,q_3$ ,a)= \delta(q_1,a)\cup \delta(q_3,a)= $q_1$\cup$q_1$=$q_1$;\\ & \delta_1($q_1, q_3$,b)= \delta(q_1,b)\cup \delta(q_3,b)= $q_1$\cup$q_1$=$q_1$. \end (تراز شده)

از آنجایی که دیگر مجموعه حالت های جدیدی وجود ندارد، روند "کشش" در اینجا به پایان می رسد و نمودار نشان داده شده در شکل را دریافت می کنیم. 7.16.

مکمل زبان معمولی

یکی از پیامدهای نظری مهم قضیه تعین، قضیه زیر است.

قضیه 7.8. مکمل یک زبان منظم، یک زبان منظم است.

بگذارید L یک زبان منظم در الفبای V باشد. سپس مکمل زبان L (به عنوان مجموعه ای از کلمات) زبان است \overline(L)=V^(\ast)\setminus L.

طبق قضیه 7.7، برای یک زبان منظم L، یک خودکار محدود قطعی M می‌تواند ساخته شود که L را بپذیرد. از آنجایی که در یک خودکار قطعی از هر راس، برای هر نماد ورودی، انتقال دقیقاً به یک راس تعریف می‌شود، بنابراین، رشته x در الفبای V هر چه باشد، یک مسیر منحصر به فرد برای آن در M وجود دارد که از ابتدایی شروع می‌شود. حالتی که در آن رشته x خوانده می شود. واضح است که رشته x توسط خودکار M، یعنی x\in L(M) مجاز است، اگر و تنها در صورتی که آخرین وضعیت مسیر مشخص شده نهایی باشد. این بدان معناست که زنجیره x\notin L(M) اگر و تنها در صورتی که آخرین وضعیت مسیر مشخص شده نهایی نباشد. اما ما فقط به یک خودکار متناهی M نیاز داریم که به زنجیره x اجازه می دهد اگر و فقط اگر خودکار متناهی اصلی M اجازه آن را ندهد. بنابراین، با تبدیل هر حالت نهایی M به حالت غیر نهایی و بالعکس، یک خودکار قطعی که امکان تکمیل زبان L را فراهم می کند.

قضیه اثبات شده به ما اجازه می دهد تا یک خودکار متناهی بسازیم که مجموعه خاصی از زنجیره ها را به روش زیر اجازه نمی دهد: ابتدا خودکاری می سازیم که مجموعه معینی از زنجیره ها را مجاز می کند، سپس آن را تعیین می کنیم و به خودکار برای مکمل منتقل می کنیم. همانطور که در اثبات قضیه 7.8 نشان داده شده است.

مثال 7.10.آ. بیایید یک خودکار متناهی بسازیم که به همه رشته ها در الفبای $0;1$ به جز رشته 101 اجازه می دهد.

اول، ما یک خودکار محدود می سازیم که امکان یک زنجیره 101 را فراهم می کند. این خودکار در شکل نشان داده شده است. 7.17.

این خودکار شبه قطعی است، اما قطعی نیست، زیرا به طور کامل تعریف نشده است. اجازه دهید آن را تعیین کنیم و یک خودکار متناهی معادل قطعی که در شکل نشان داده شده است به دست آوریم. 7.18.

و در نهایت، با عبور از اضافه (و تغییر نام حالت ها)، خودکار نشان داده شده در شکل را دریافت می کنیم. 7.19.

توجه داشته باشید که در خودکار به دست آمده، تمام رئوس به جز راس s_3، نهایی هستند.

همچنین توجه داشته باشید که انتقال به متمم، که در اثبات قضیه 7.8 مورد بحث قرار گرفته است، فقط در یک خودکار قطعی قابل انجام است. اگر نقش رئوس نهایی و غیر نهایی را در خودکار نشان داده شده در شکل معکوس کنیم. 7.17، ما خودکاری دریافت می کنیم که زبان $\lambda,1,10$ را می پذیرد، که - همانطور که به راحتی قابل مشاهده است - مجموعه تمام رشته ها به جز رشته 101 نیست.

همچنین توجه داشته باشید که ماشین حالت محدود در شکل. 7.19 به تمام رشته هایی که دارای یک رخداد از رشته 101 هستند اما با خود رشته مطابقت ندارند اجازه می دهد. برای مثال، مسیر حامل زنجیره 1011 در اینجا آمده است: s_0،s_1،s_2،s_3،t.

ب اجازه دهید یک خودکار متناهی بسازیم که به همه رشته‌ها در الفبای $0;1$ اجازه می‌دهد به جز رشته‌هایی که حاوی یک رخداد از رشته 101 هستند. یک زبان L را در نظر بگیرید که هر رشته آن حاوی یک رخداد از رشته 101 است. به صورت زیر تعریف شده است:

L=(0+1)^(\ast)101(0+1)^(\ast).

ما باید یک خودکار برای تکمیل زبان L بسازیم.

مستقیماً از عبارت منظم در این مورد، ساخت یک خودکار محدود که به زبان L اجازه می دهد آسان است (شکل 7.20).

سپس با روش "کشیدن" تعیین را انجام می دهیم. نتیجه تعیین در شکل نشان داده شده است. 7.21.

برای حل کامل مشکل، فقط شکل. 7.21 نقش رئوس نهایی و غیر نهایی را عوض کنید (شکل 7.22).

که در. بیایید ایده ساخت یک خودکار محدود را مورد بحث قرار دهیم که به آن رشته‌ها و فقط رشته‌هایی در الفبا $0;1$ اجازه می‌دهد که با رشته 01 شروع نمی‌شوند و به رشته 11 ختم نمی‌شوند (یعنی رشته‌های از فرم 01x و رشته های فرم y11 مجاز نیستند، هر چه زنجیره های x,y\in$0;1$ وجود داشته باشد).

در این مورد، مکمل زبانی که می‌خواهید برای آن یک خودکار متناهی بسازید، مجموعه تمام رشته‌های صفر و یک است که با رشته 01 شروع یا با رشته 11 ختم می‌شود. خودکاری که این مجموعه رشته‌ها را می‌پذیرد. به عنوان یک خودکار برای ترکیب ساخته شده است 01(0+1)^(\ast)+(0+1)^(\ast)11به همان شیوه ای که در اثبات قضیه کلین (به قضیه 7.6 مراجعه کنید).

ویژگی کلاس زبان‌های منظم که تحت مکمل بسته می‌شوند (به قضیه 7.8 مراجعه کنید) بلافاصله نشان می‌دهد که این کلاس تحت تفاوت‌های تقاطع، تئوری مجموعه‌ها و متقارن بسته می‌شود.

نتیجه 7.3. برای هر دو زبان معمولی L_1 و L_2، عبارات زیر درست است:

1) تقاطع L_1\cap L_2 منظم است.
2) تفاوت L_1\setminus L_2 منظم است.
3) اختلاف متقارن L_1\مثلث L_2منظم.

اعتبار اظهارات از هویت ها به دست می آید:

\begin(تراز شده) &(\scriptstyle(\mathsf(1)))\quad L_1\cap L_2= \overline(\overline(L_1) \cup\overline(L_2))\,;\\ &(\scriptstyle (\mathsf(2))))\quad L_1\setminus L_2= L_1\cap \overline(L_2)\,;\\ &(\scriptstyle(\mathsf(3))))\quad L_1\,\مثلث\ ,L_2 = (L_1\کاپ L_2)\setminus (L_1\cap L_2).\end (تراز شده)

ابتدا، نتایج به‌دست‌آمده به ما امکان می‌دهد ادعا کنیم که کلاس زبان‌های منظم با توجه به عملیات اتحاد، تقاطع و جمع یک جبر بولی است که در آن واحد زبان جهانی و صفر زبان خالی است. . ثانیاً، این ویژگی‌های جبری خانواده زبان‌های منظم به ما امکان می‌دهد مشکل مهم تشخیص معادل دو خودکار محدود دلخواه را حل کنیم.

طبق تعریف 7.10، خودکارهای متناهی در صورتی معادل هستند که زبان های مجاز آنها یکسان باشد. بنابراین، برای تأیید هم ارزی خودکار M_1 و M_2، کافی است ثابت کنیم که تفاوت متقارن زبان های L(M_1) و L(M_2) خالی است. برای انجام این کار، به نوبه خود، ساخت خودکاری که این تفاوت را بپذیرد و تأیید کند که زبانی که می پذیرد خالی است، کافی است. به طور کلی، مشکل تشخیص خالی بودن زبان ماشین حالت، مسئله خالی بودن ماشین حالت نامیده می شود. برای حل این مشکل، کافی است مجموعه حالت های نهایی خودکار را که از حالت اولیه قابل دسترسی هستند، بیابیم. از آنجایی که ماشین حالت محدود یک گراف جهت دار است، این مشکل را می توان به عنوان مثال با استفاده از جستجوی عرضی حل کرد. زبان مجاز توسط خودکار محدود اگر و تنها در صورتی خالی است که مجموعه حالت های نهایی قابل دستیابی از حالت اولیه خالی باشد. در عمل، تشخیص هم ارزی خودکارهای محدود با استفاده از الگوریتم کمینه سازی ترجیح داده می شود، اما اکنون برای ما مهم است که تأکید کنیم که امکان اساسی حل مسئله هم ارزی از قضیه 7.7 و پیامدهای جبری آن ناشی می شود.

دسته بندی ها

مقالات محبوب

	ده نشانه عشق مرد به زن - رفتار عاشق
	چهار مرحله زندگی و مرگ در آیورودا
	عاشقانه ترین و دوست داشتنی ترین نشانه های زودیاک
	چگونه بفهمیم که یک زن شما را دوست ندارد (نشانگر این است که وقت آن رسیده است که به دنبال یک مورد جدید بگردید)؟
	«صدای سفید» و مذاکره با دنیای مردگان

2022 "kingad.ru" - بررسی سونوگرافی اندام های انسان