pdf تئوری خودکار. تئوری خودکار

Z A 79 نظریه مسلسل ها: دستورالعمل هابرای آموزش عملی برای تخصص 230101 / T.Z. آرالبایف،<...>دستورالعمل ها را پوشش می دهد سوالات زیر: راه های ارائه منطقیتوابع ( LF) تبدیل جبری LF; روش های کمینه سازی کواینو مک کلاسکی با استفاده از نقشه ها کارنو; فرم ها تکالیف نهایی مسلسل ها; سنتز ترکیبی طرح هادر اساس " و نه” (“یا نه") در منطقی عناصرسری K155 و K561.<...>دستورالعمل های روشی برای سازماندهی کلاس های عملی در این دوره در نظر گرفته شده است. نظریه مسلسل ها” برای دانشجویان سال دوم در تخصص 230101 ” کامپیوترهامجتمع ها، سیستم ها و شبکه ها.<...>به حداقل رساندن توابع منطقیتوسط کارت کارنو ……………………….. <...>41 3 مقدمه این دستورالعمل حاوی مطالبی برای برگزاری کلاس های عملی در یکی از بخش های اصلی رشته "نظریه" است. مسلسل ها” – “مبانی منطقی دیجیتال مسلسل ها”. <...>1.1 شکل جدولی نمایش LF تابع منطقی به وضوح توسط جداول حقیقت(TI) و کارت ها کارنو. <...> جدول حقیقت- این جدول، که در آن هر مجموعه باینری از مقادیر آرگومان xi (i = 1, n) با مقدار تابع Y = f (x1, x2,..., xi,..., xn) در ارتباط است. این مجموعه. <...>نقشه Carnaugh یک جدول مستطیل شکل شامل n 2 خانه است که هر خانه در تقاطع ردیف i و ستون j قرار دارد، ai و aj عناصر تشکیل دهنده هستند. باینری استخدام n - LF محلی.<...>1) هر جفت سلولی که به صورت عمودی یا افقی مجاور هستند، و همچنین هر جفت سلولی که به صورت متقارن روی نقشه به صورت عمودی یا افقی قرار گرفته اند، مطابقت دارند. باینری مجموعه ها، که در مقدار تنها یک متغیر متفاوت است (یعنی در یک رقم متفاوت است).<...>2) در سلول ها کارت ها Carnot مقادیر تابع را در مجموعه مربوطه نشان می دهد.<...>3) مجموعه‌های باینری آرگومان‌هایی که ردیف‌ها را علامت‌گذاری می‌کنند، و همچنین مجموعه‌های باینری از آرگومان‌هایی که ستون‌ها را علامت‌گذاری می‌کنند.<...>

Theory_automata.pdf

UDC 004.3(076.5) BBK 32.97ya73 A 79 بازبین: دکتر علوم فنی، پروفسور ع.م. پیشچوخین آرالبایف، T.Z A 79 نظریه اتوماتا: دستورالعمل های روش شناختی برای تمرینات عملی برای تخصص 230101 / T.Z. آرالبایف، I.V. ژوکالینا. - اورنبورگ: موسسه آموزشی دولتی OSU، 2009. - 41 ص. دستورالعمل ها به مسائل زیر می پردازند: روش های نمایش توابع منطقی (LF). تبدیل جبری LF. روش های کمینه سازی کواین و مک کلاسکی با استفاده از نقشه های کارناو. فرم هایی برای تعیین ماشین های حالت محدود. سنتز مدارهای ترکیبی مبتنی بر "AND-NOT" ("OR-NOT") بر روی عناصر منطقی سری K155 و K561. این دستورالعمل برای سازماندهی کلاس های عملی در درس "تئوری اتوماتا" برای دانش آموزان سال دوم در تخصص 230101 "کامپیوترها، مجتمع ها، سیستم ها و شبکه ها" در نظر گرفته شده است. BBK 32.97ya73 © Aralbaev T.Z.، 2009 © Zhukalina I.V.، 2009 © موسسه آموزشی دولتی OSU، 2009 2

صفحه 2

مقدمه مطالب ................................................ ................................................... ......... ...................4 1 درس عملی شماره 1. روش‌های نمایش توابع منطقی………………………………….… 5 1.1 شکل جدولی ارائه LF………………………………………….5 1.2 شکل تحلیلی ارائه LF ………………………………………….۸ ۲ درس عملی شماره ۲. تبدیل جبری فرمول های توابع منطقی………….…..12 2.1 قوانین جبر بولی………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………. …………………………………………..12 3 درس عملی شماره 3. روش کمینه سازی کواین و مک کلاسکی………………………………………….15 3.1 یافتن همه ایمپلنت های اول………………………………………………..15 3.2 ساخت جدول پوشش کواین ماتریس ها………………………………16 3.3 یافتن حداقل پوشش یک تابع…………………………………………….16 3.4 به دست آوردن حداقل شکل LF…………… …………16 4 درس عملی شماره 4. به حداقل رساندن توابع منطقی با استفاده از نقشه های کارنو…………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………….21 4.2 ساخت حداقل CNF… ………………………………………………………………….22 4.3 به حداقل رساندن LFهای ناقص تعریف شده…………………………………………………………………………………………………………………………………………………………………………………………….. ۲۳ ۵ درس عملی شماره ۵ فرم‌هایی برای تعیین متناهی ماشین‌های حالت……………………………………………………………..۲۵ ۶ درس عملی شماره ۶ سنتز مدارهای ترکیبی بر اساس «AND-NOT» («OR-NOT»)………. ………30 7 درس عملی شماره 7. سنتز مدارهای ترکیبی بر اساس عناصر منطقی سری K155 و K561…………………………………………………………………………………………… ...35 فهرست منابع مورد استفاده................................................... ...................................... 40 پیوست…………………………………………… ………………………………………41 3

صفحه 3

مقدمه این دستورالعمل ها حاوی مطالبی برای برگزاری کلاس های عملی در یکی از بخش های اصلی رشته "تئوری اتوماتا" - "مبانی منطقی اتوماتای ​​دیجیتال" است. هدف از کلاس ها ادغام عملی دانش در مورد اشکال نمایش و روش های تبدیل توابع منطقی و همچنین روش سنتز مدارهای ترکیبی است. هر درس عملی شامل تعیین هدف درس، مطالب نظری مختصر در مورد موضوع، مثال های معمولی، سوالات تستیو تمرین هایی برای کار مستقل. قبل از اجرای درس، دانش آموز باید هدف آن را بفهمد و به سوالات کنترلی پاسخ دهد. برای آمادگی مستقل برای کلاس ها، به دانش آموزان توصیه می شود ادبیات ارائه شده در فهرست منابع مورد استفاده را مطالعه کنند. در طول درس، مثال ها تجزیه و تحلیل می شود و تمرین ها بر اساس گزینه ها انجام می شود. کنترل دانش بر اساس نتایج پاسخ به سوالات آزمون و تکمیل تمرینات انجام می شود. 4

صفحه 4

1 درس عملی شماره 1. اشکال نمایش توابع منطقی اشکال مختلفی از نمایش توابع منطقی (LF) در مراحل مختلف طراحی مدارهای ترکیبی استفاده می شود، به ویژه: کلامی، جدولی، تحلیلی، هندسی، مکعبی. هدف درس عملیمطالعه اشکال جدولی و تحلیلی نمایش LF و الگوریتم هایی برای انتقال از توصیف جدولی LF به توصیف تحلیلی است. 1.1 شکل جدولی نمایش LF تابع منطقی به وضوح با استفاده از جدول حقیقت (TI) و نقشه کارناگ نشان داده می شود. جدول صدق جدولی است که در آن هر مجموعه باینری از مقادیر آرگومان xi (i = 1, n) با مقدار تابع Y = f (x1, x2,..., xi,..., xn) در این مجموعه. جدول 1.1 تابع TI را برای سه آرگومان به عنوان مثال نشان می دهد. تابع Y مقدار 1 یا 0 را در هر مجموعه می گیرد. اگر مقدار تابع تعریف نشده باشد، یک خط تیره در موقعیت مربوطه TI قرار می گیرد. جدول 1.1 – جدول حقیقت تابع منطقی N Х1 Х2 Х3 Y 0 0 0 0 1 1 0 0 1 1 2 0 1 0 0 3 0 1 1 1 4 1 0 0 0 5 1 0 1 0 6 1 1 0 0 0 1 1 2 0 1 0 0 0 0 1 1 1 4 1 0 0 0 5 1 0 1 0 6 1 0 1 7 1 1 1 1 گاهی اوقات از فرم لیستی از نمایش TI استفاده می شود که لیستی از مجموعه های یک و صفر را ارائه می دهد. بنابراین، تابع در نظر گرفته شده در مثال در فرم لیست را می توان به صورت: Y = F Х Х Х) = ∨ (0, 1, 3, 6, 7) Y = ∧ (2, 4, 5) (0 1, 2، 3 1 5

وزارت آموزش و پرورش فدراسیون روسیهنیژنی نووگورود دانشگاه دولتیآنها N.I. لوباچفسکی

دانشکده ریاضیات محاسباتی و سایبرنتیک

توسعه آموزشی و روش شناختی برای کار مستقل دانش آموزان در درس "نظریه الگوریتم ها و منطق ریاضی"

ضمن مطالعه مبحث مفاهیم ماشین حالت محدود و زبان منظم. عملیات روی زبان های معمولی"

نیژنی نووگورود 2000

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

گردآوری شده توسط:

معلمان گروه انفورماتیک و اتوماسیون تحقیقات علمی دانشکده ریاضیات محاسباتی و ریاضیات UNN دانشیار، دکترای علوم فنی کوگان دی.آی. و دستیار بابکینا ت.س.

1. مفهوم زبان، مثال هایی از زبان ها، عملیات روی زبان ها.

حروف الفبا مجموعه‌ای از علامت‌های محدود غیر خالی دلخواه است. به کاراکترهای یک الفبای دلخواه حروف می گویند. به عنوان نمونه، الفبای روسی (با یا بدون گنجاندن علائم نگارشی)، الفبای لاتین، ترکیبی از این الفبا و ارقام بسیاری از سیستم های اعشاری یا دودویی را نشان خواهیم داد. به طور کلی، ما الفبا را به عنوان یک مجموعه A = (a 1, a 2, ..., a n) تعریف می کنیم. در میان حروف الفبای الف نیز ممکن است شخصیت خاصفاصله (حرف خالی)، این نماد معمولا e نشان داده می شود (مخفف انگلیسی "خالی" - خالی).

یک کلمه در الفبای A یک دنباله متناهی دلخواه از حروف آن است. یک حرف می تواند چندین بار در این دنباله ظاهر شود. طول کلمه α (نشان l(α)) تعداد حروف این کلمه است. نماد ویژه λ تنها کلمه ای را نشان می دهد که طول آن صفر است (کلمه خالی). باید بین یک کلمه خالی و یک کلمه e متشکل از یک حرف خالی تمایز قائل شد. طول کلمه e (فاصله) برابر با یک است. در الفبای A = (a 1, a 2, ..., a n) می توانید n l کلمه مختلف با طول l بنویسید که در آن l = 0، 1، 2، .... مجموعه تمام کلمات الفبای A با A * نشان داده می شود. مخصوصاً توجه داشته باشیم که مجموعه A * شامل کلمه خالی نیز می شود. کاردینالیته مجموعه همه کلمات الفبای الف قابل شمارش است.

اگر α و β دو کلمه دلخواه در الفبای A باشند، αβ نتیجه انتساب کلمه β به کلمه α در سمت راست است. برای هر کلمه α و β فرض می کنیم که

αλ= λα= α, αλβ= αβ.

زبان در الفبای A زیرمجموعه دلخواه کلمات L از A * است. اگر زبانی شامل مجموعه متناهی از کلمات باشد، L را محدود می نامیم. یک زبان L بی نهایت است اگر شامل بی نهایت کلمه باشد. کلیت تمام کلمات روسی، همه کلمات زبان انگلیسینمونه هایی از زبان های محدود هستند. مجموعه ای از رکوردهای تمام اعداد اول به صورت اعشاری یا سیستم باینریاعداد یک زبان بی نهایت هستند. مجموعه همه زبان‌های الفبای A دارای ویژگی پیوستگی هستند.

زبان L در الفبای A اگر L=A * باشد، جهانی نامیده می شود. زبان L

اگر مجموعه L خالی باشد آن را خالی می نامیم (L =).

بگذارید L 1 و L 2 زبان های الفبای A باشند. از طریق L 1 L 2 و L 1 ∩ L 2 خواهیم کرد

به ترتیب نشان دهنده اتحاد و تلاقی این زبان ها است. کلمه α متعلق به اتحاد دو زبان است اگر حداقل به یکی از آنها تعلق داشته باشد. کلمه α به محل تلاقی دو زبان تعلق دارد اگر هم به یکی و هم به زبان دیگر تعلق داشته باشد. بگذارید L یک زبان در الفبای A باشد. بگذارید L c نشان دهنده مکمل این زبان باشد. زبان L c توسط کلمات الفبای A که بخشی از زبان L نیستند تشکیل می شود: L c = A *\L. عمليات اتحاد، تقاطع و جمع، عمليات تئوري مجموعه اساسي هستند.

بگذارید L 1 و L 2 زبان های الفبای A باشند. ما با L 1 \ L 2 نشان خواهیم داد

تفاوت بین زبان های L 1 و L 2. کلمه α از A * به L 1 \L 2 تعلق دارد اگر و فقط اگر متعلق به زبان L 1 باشد، اما به زبان L 2 تعلق ندارد. بدیهی است که عملیات تفاوت را می توان از طریق نظری پایه نشان داد

عملیات چندگانه: L 1 \L 2 =L 1 ∩ (L 2 )с.

علاوه بر این، چندین عملیات ویژه روی زبان ها را معرفی می کنیم. بگذارید L 1 و L 2 زبان های الفبای A باشند. بگذارید L 1 ( L 2 نشان دهنده زبان باشد

به صورت زیر تعریف می شود: کلمه α متعلق به زبان L 1 ( L 2 اگر و فقط اگر این کلمه به دو قسمت متوالی تقسیم شود تعلق دارد.

(یعنی به شکل α = α 1 α 2 ارائه شده است) به طوری که قسمت اول کلمه ای از زبان L 1 و قسمت دوم کلمه ای از زبان L 2 است. عملیات ( الحاق (پیوند دادن) زبان ها نامیده می شود. علامت ( اغلب حذف می شود، سپس الحاق زبان ها L 1 و L 2 L 1 L 2 نوشته می شود. زبان L 1 L 2 با افزودن کلمات به دست می آید. از زبان L 2 به کلمات زبان L 1 به عنوان پایان، توجه داشته باشید که اگر یک کلمه خالی به یک کلمه دلخواه γ اضافه شود، اگر زبان L 1 و L 2 محدود باشد، نتیجه می شود. و زبان اول حاوی m کلمه و زبان دوم حاوی n کلمه است، سپس زبان L 1 L 2. حداکثر از mn کلمه تشکیل شده است، اگر یکی از زبان ها L 1، L 2 خالی باشد، L 1 L 2 نیز یک زبان خالی است.

اجازه دهید عملیات ارتقاء زبان به یک قدرت را معرفی کنیم. ما معتقدیم:

L 0 =(λ);

L1 = L;

L2 = LL; Ln +1 = Ln L، n=2، 3، ...;

بنابراین، مفهوم درجه L i زبان L برای هر i = 0، 1، 2، 3 تعریف می شود،

L* =U Li.

i=0

عملیات معرفی شده تکرار نامیده می شود. توجه داشته باشید که کلمه خالی متعلق به تکرار هر زبانی است. یک کلمه غیر خالی α متعلق به تکرار زبان L است اگر و تنها در صورتی که این کلمه را بتوان به تعدادی قسمت (زیرکلمه) متوالی تقسیم کرد به طوری که هر قسمت متعلق به زبان L باشد. اگر زبان L از تمام کلمات تک حرفی الفبای A تشکیل شده باشد، تکرار این زبان، زبان جهانی A* است. توجه داشته باشید که برای هر زبان L (L *)*=L * داریم.

در بسیاری از زبان‌ها، عملگر unary ()+ زیر گاهی در نظر گرفته می‌شود:

(L )+ =U L i.

i=1

زبان های L * و L + فقط در یک کلمه خالی با یکدیگر تفاوت دارند. کلمه λ همیشه متعلق به زبان L * است. به زبان L + تعلق دارد اگر و فقط اگر متعلق به زبان L باشد.

2. مفاهیم ماشین حالت محدود و زبان منظم.

در سایبرنتیک، اتومات ها ماژول هایی هستند که از نظر فنی یا نرم افزاری پیاده سازی شده اند که برای پردازش اطلاعات دریافتی طراحی شده اند. ماشین حالتماژولی است که دارای تعداد محدودی از حالت های ممکن است و در زمان گسسته عمل می کند. در این آموزش، ماشین های حالت محدود به عنوان دستگاه های الگوریتمی انتزاعی طراحی شده برای پردازش کلمات یک الفبای ورودی ثابت مورد مطالعه قرار می گیرند. ما فرض می کنیم که خودکار پردازش یک کلمه دلخواه α در الفبای ورودی A را از یک حالت اولیه انتخاب شده شروع می کند. در هر ساعت زمان گسسته، حرف بعدی از کلمه در حال پردازش به ورودی ماشین می رسد که تحت تأثیر آن است، ماشین حالت خود را تغییر می دهد. حالتی که ماشین به آن وارد می شود با حالت قبلی و حرف خوانده شده کلمه ورودی تعیین می شود. دستگاه بر روی یک کلمه به طول l چرخه کار می کند. نتیجه عملکرد ماشین با وضعیتی که پس از اتمام کار در آن قرار دارد تعیین می شود.

به طور رسمی، ما یک خودکار محدود K را به عنوان یک مجموعه تعریف می کنیم

K=(Q، A، q0، g، F)،

که در آن Q = (q 0، q 1، q 2، ...، q m) - مجموعه ای از حالت های خودکار. A = (a 1, a 2, ..., a n) – الفبای ورودی; q 0 - یک حالت خاص انتخاب شده از ماشین که حالت اولیه نامیده می شود. g - تابع انتقال ماشین محدود،

که یک نگاشت از نوع Q xA → Q است (اگر g (q i,a j)=q k، پس خودکار از حالت q i تحت تأثیر حرف a j باید به حالت q k برود). F زیرمجموعه ای خاص از حالت های خودکار انتخاب شده است که ما معمولاً آن را "خوب"، F Q می نامیم.

حالتی که خودکار K بعد از t چرخه کار روی این کلمه در آن قرار می گیرد (در اینجا t = 0, 1, 2, ..., p):

qα (0) =q0 ;

q α (1) = g (q α (0)، a i 1)

q α (2) = g (q α (1)، a i 2)

q α (p) = g (q α (p - 1)، a i p)

اگر q α (р) F باشد، خواهیم گفت که کلمه α توسط خودکار K پذیرفته می شود.

اجازه دهید زبان L(K) را معرفی کنیم: اگر این کلمه توسط خودکار K پذیرفته شود، کلمه α متعلق به زبان L(K) است. زبان L(K) زبانی است که توسط این ماشین حالت محدود شناخته می شود. اگر بتوانیم یک خودکار متناهی برای آن بسازیم، زبانی را L منظم می نامیم.

تعریف یک ماشین حالت محدود با نمودار انتقال آن راحت است. نمودار یک نمودار جهت دار است که رئوس آن با حالت های خودکار یکسان است. یک قوس از راس q i به راس q k با حرف a j که بالای آن نوشته شده باشد کشیده می شود اگر و فقط اگر g (q i,a j)=q k. در صورتی که انتقال از q i به q k تحت تأثیر هر یک از حروف یک زیرمجموعه خاص S, S A انجام شود، تمام حروف این زیر مجموعه در بالای قوس مربوطه امضا می شوند (به جای فهرستی از همه حروف، ورود به اختصار "x S" یا به سادگی "S" مجاز است). اگر حالت دلخواه q i در F گنجانده شود، این واقعیت با دایره ای ضخیم که راس q i را برجسته می کند، روی نمودار مشخص می شود.

بدیهی است که هر ماشین حالت محدود به طور کامل توسط نمودار انتقال آن تعریف می شود. علاوه بر این، وظیفه ساخت یک اتومات محدود با خواص معین به عنوان وظیفه ساختن نمودار انتقال آن درک خواهد شد.

در شکل شکل 2.1 نموداری از خودکار K 1 را نشان می دهد که بر روی کلمات الفبای A =(a,b,c) کار می کند. اتومات دارای دو حالت q 0 و q 1 است و فقط حالت q 1 "خوب" است. با شروع کار در حالت q 0، دستگاه تحت تأثیر حروف a، b از این حالت خارج نمی شود. تحت تأثیر حرف c، انتقال به حالت q 1 تحقق می یابد. هر نامه دیگری که می رسد دستگاه را در همان حالت باقی می گذارد. بنابراین، خودکار K 1 زبان L 1 را که از کلمات حاوی حرف c تشکیل شده است، تشخیص می دهد. این زبان منظم است.

q0 q1

بیایید چند مثال دیگر از زبان های معمولی را در همان الفبا ارائه دهیم: L 2 - مجموعه ای از کلمات که در آن حرف a چند بار زوج اتفاق می افتد. L 3 - مجموعه ای از کلمات که با همان حرف شروع و ختم می شوند. L 4

مجموعه ای از کلمات حاوی زیرکلمه α =abbc ; L 5 مجموعه ای از کلمات است، هنگام خواندن از چپ به راست، تفاوت بین تعداد حروف a و b هرگز از 2 تجاوز نمی کند. نمودارهای ماشین های حالت محدود K 2 - K 5 که زبان ها را تشخیص می دهند L 2 - L 5 به ترتیب در شکل های 2.2 - 2.5 ارائه شده است. ماشین اطلاعات مربوط به قسمت پردازش شده کلمه ورودی را بر اساس وضعیت آن "به خاطر می آورد". بنابراین، به عنوان مثال، خودکار K 5، با پردازش بخشی از کلمه ورودی، خود را در حالت q x می یابد اگر در بخشی از کلمه ورودی که خوانده، تعداد حروفی که a با آن مواجه می شود بیشتر از تعداد حروف b باشد. x; در اینجا x (-2، -1، 0، 1، 2)؛ اگر در نقطه‌ای از عملکرد خودکار قدر مطلق تفاوت بین تعداد حروف پردازش‌شده a و تعداد حروف پردازش‌شده b از 2 بیشتر شود، خودکار در وضعیت q بد است.

		q بد

اگر هر حرف ورودی اتومات را از این حالت خارج نکند، حالت جذب خودکار محدود را می نامیم. بیایید حالت جذب را نام ببریم جذب مثبت، اگر متعلق به F باشد و جذب منفیدر غیر این صورت. در اتومات K 1 و K 4، حالات q 1 و q 4 به ترتیب جذب مثبت هستند، در خودکار K 5، حالت q بد جذب منفی است.

می توانیم فرض کنیم که هر خودکار بیش از یک حالت جذب مثبت و بیش از یک حالت جذب منفی ندارد (اگر چندین حالت جذب مثبت یا منفی وجود داشته باشد، به راحتی می توان آنها را با یکی جایگزین کرد). به طور معمول، حالت جذب منفی در یک نمودار انتقال نشان داده نمی شود. اگر انتقال از یک حالت خاص توسط یک حرف مشخص نشان داده نشود، فرض می شود که منجر به یک حالت جذب منفی می شود. ماشین متناهی نشان داده شده در شکل 2.6 در الفبای A زبانی متشکل از کلماتی را می شناسد که در آن حرف c دقیقا یک بار ظاهر می شود. این خودکار دارای 3 حالت است، حالت جذب منفی q بد است (اتومات از حالت q 1 مطابق حرف c وارد آن می شود) در نمودار نشان داده نشده است.

q0 q1

اجازه دهید الفبای B =(0، 1، 2، …، 9) را معرفی کنیم، هر کلمه در این الفبا به عنوان یک عدد صحیح غیر منفی در نظر گرفته می شود. اجازه دهید L (p) مجموعه ای از کلمات را نشان دهد - رکوردهایی در سیستم اعداد اعشاری همه اعداد صحیح غیر منفی که مضرب ثابت طبیعی p هستند. فرض می کنیم که زبان L (p)

علاوه بر این، کلمه خالی λ نیز متعلق است. اجازه دهید نشان دهیم که L (p) یک زبان منظم است. یک خودکار محدود K(p) که L(p) را تشخیص می دهد می تواند به صورت زیر ساخته شود. ما حالت های خودکار را q 0، q 1، q 2، q p –1 در نظر می گیریم. از یک حالت دلخواه q i با رقم x، x (0، 1، 2، ...، 9)، ماشین به

A.A. تئوری اتومات اوزیگانف. کتاب درسی - سنت پترزبورگ: NRU ITMO، 2013. - 84 ص. - کپی کنید

حاشیه نویسی:

هدف این کتاب درسی آشنایی دانش آموزان با روش های سنتز اتوماتای ​​دیجیتال است. اطلاعاتی در مورد خودکارهای انتزاعی میلی و مور ارائه شده است. روش‌های جدولی و نموداری برای نمایش خودکارها در نظر گرفته می‌شوند، مفهوم واکنش خودکار به یک کلمه ورودی و تعریف خودکارهای معادل معرفی می‌شوند. روش‌هایی برای تبدیل معادل متقابل خودکارها ارائه شده‌اند. داده می شوند اطلاعات عمومیدر مورد کنترل ریزبرنامه، مفاهیم ریزدستورالعمل ها، ریزعملیات، ریزبرنامه ها، روش های نمایش ریزبرنامه ها در قالب نمودارهای نموداری الگوریتم ها (GDA)، فرمول های انتقال، ماتریس و نمودارهای منطقی الگوریتم ها. روش‌هایی برای علامت‌گذاری GSA و قوانین ساخت خودکار Mealy و Moore با استفاده از آنها آورده شده است. روش‌هایی برای سنتز متعارف اتوماتای ​​ساختاری در نظر گرفته شده‌اند. نمونه هایی از سنتز حافظه یک اتومات ساختاری بر اساس فلیپ فلاپ های D -، T -، RS - و JK ارائه شده است.

توضیحات:

این راهنما برای دانشجویان متخصص در این زمینه در نظر گرفته شده است فناوری اطلاعاتو قابل استفاده در آماده سازی کارشناسی و کارشناسی ارشد در رشته های 230100 ” انفورماتیک و تکنولوژی کامپیوتر"، 231000 "مهندسی نرم افزار" و مهندسان در تخصص 230101 "کامپیوتر، مجتمع ها، سیستم ها و شبکه ها."

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

مرحله 1. کتاب ها را از کاتالوگ انتخاب کنید و روی دکمه "خرید" کلیک کنید.

مرحله 2. به بخش "سبد خرید" بروید.

مرحله 3. مقدار مورد نیاز را مشخص کنید، داده ها را در بلوک های گیرنده و تحویل پر کنید.

مرحله 4. روی دکمه "Proceed to Payment" کلیک کنید.

روشن در حال حاضرخرید کتاب چاپی، دسترسی الکترونیکی و یا کتاب به عنوان هدیه به کتابخانه در سایت EBS تنها با پیش پرداخت 100% امکان پذیر است. پس از پرداخت، به شما امکان دسترسی به متن کامل کتاب درسی در کتابخانه الکترونیکی داده می شود یا ما در چاپخانه شروع به تهیه سفارش برای شما می کنیم.

توجه! لطفا روش پرداخت خود را برای سفارشات تغییر ندهید. اگر قبلاً یک روش پرداخت را انتخاب کرده‌اید و نتوانسته‌اید پرداخت را تکمیل کنید، باید دوباره سفارش را ثبت کنید و با استفاده از روش مناسب دیگری هزینه آن را پرداخت کنید.

شما می توانید با استفاده از یکی از روش های زیر هزینه سفارش خود را پرداخت کنید:

1. روش بدون نقد:
   • کارت بانکی: باید تمام فیلدهای فرم را پر کنید. برخی از بانک ها از شما می خواهند که پرداخت را تأیید کنید - برای این، یک کد SMS به شماره تلفن شما ارسال می شود.
   • بانکداری آنلاین: بانک هایی که با سرویس پرداخت همکاری می کنند فرم خود را برای پر کردن ارائه می دهند.
     لطفا داده ها را در تمام فیلدها به درستی وارد کنید. به عنوان مثال، برای" class="text-primary">Sberbank Online تعداد مورد نیازتلفن همراه و ایمیلشما نیاز به ورود به سرویس Alfa-Click و یک ایمیل دارید.
   • کیف پول الکترونیکی: اگر کیف پول Yandex یا کیف پول Qiwi دارید، می توانید هزینه سفارش خود را از طریق آنها پرداخت کنید. برای انجام این کار، روش پرداخت مناسب را انتخاب کرده و فیلدهای ارائه شده را پر کنید، سپس سیستم شما را به صفحه ای جهت تایید فاکتور هدایت می کند.