Studopediya

КАТЕГОРИЯ:


Основни понятия на детерминирана крайни автомати




Тема 5.2. Детерминистични крайни автомати

Кратко описание на

Преглед въпроси

1.Konechny машина е?

2. В каква е разликата на държавната машина и машина?

3.Nazovite комплекти, които описват държавна машина?

4.Privedite разлика модел автомат щитоносна и Мур?

5.Privedite начини за уточняване машини?

6. Тъй като преходът от модела на щитоносна автомат Мур ФЩМ?

7. Как е преходът от модела на Мур FSM щитоносна автомат?

8.Sformuliruyte предимствата и недостатъците на различните методи за автоматична работа?

9. Каква е функцията на прехода?

Това показва метод за с помощта на крайни автомати за вземане на решения. Като се имат предвид основните характеристики и докладване на крайни автомати. Разкрити структурата на машината, с неговия набор от комплекта, като например, като множество от входни и изходни стойности. Методите за определяне машини. Са най-често използваните машини миля и Мур, както и покаже разликата им в експлоатация. Взаимовръзката между моделите и машините Mile Мур, който илюстрира преходът от един модел към друг и обратно.

Цел: Да се запознаят с детерминирана крайни автомати.

Цели:

Помислете 1. основни понятия от детерминирана крайни автомати.

2. За да се учат на схемата за доказване на коректността на машината.

3. Покажете как машините работят.

Крайни автомати често се използват за определяне на някои свойства на думи, т.е. за разпознаване на езика: автоматичен, признава някои език L трябва да бъде в произволна дума w отговори на въпроса w L? , За да се реши този проблем функцията за изход може да бъде заменен от тест, в който държавата става автоматично след получаване на входящ дума w бъде приета или отхвърлена.

Детерминистични крайни автомати (DFA) - за преобразуване - е система от формата

A = <Σ, Q, Q 0, F, Φ,>,

включва следните компоненти:

Σ = {1 ,. , , , A m} (m ≥ 1) ограничен набор - вход азбука;

Q = {Q 0. , , , Q н -1} (п ≥ 1) ограничен набор - азбука на вътрешни състояния;

Q 0 Q първоначалното състояние;

F Q набор от решения (позволява, окончателен) се посочва;

Φ: Q × Σ → Q преход функция, Φ (Q, а) е състояние, при което машината преминава от състоянието на р, когато тя получава на входа на характера на.

Cp функция се нарича програма на автомат А и се дава под формата на списък от команди, Mn видове р аз едно й → Φ (р аз, а й).

Също така е удобно да настроите функция МФ чрез използване на горната таблица на размера н м, където редовете съответстват на състоянията на Q, и колоните на символи в Σ входната азбука, където в пресечната точка на ред и колона р аз едно й стои състояние Φ (Q аз, а й) .



Подобно на машини, трансформатори, автоматични-разпознаване на може да бъде представляван от етикетирани насочени графики, диаграми, наречени.

Графика DFA A = <Σ, Q, Q 0, Φ> е насочено мултиграф D A = (Q, E) с белязани ръбове, в който се изтъква в горната част на първоначалното състояние Q 0 от всеки връх р Q Output | Σ X | ръбове, маркирани с Σ такова, че за всеки р Q и всеки символ Σ има уникален ръб на върха на р q0 = Φ (Q, а) да се маркира.

Ние казваме, че последователността на ръбове, представлявана от пътя р = д 1 е 2. , , д т в диаграмата носи думата w = w 1 W 2. , , w т, w и ако е ръб етикет д аз (1 ≥ аз ≥ т). Ако р е първоначалната връх (състояние) на пътя, и Q 'окончателното си връх, тогава казваме, че една дума w отнема р до р ".

работа краен автомат-Резолвер е четенето на входния думата и промените държави в зависимост от неговия характер.

Конфигурация DFA A = <Σ, Q, Q 0, F, Φ,> - тип е произволна двойка (Q, W), където Q Q и W Σ * (Припомняме, че Σ * означаваме множеството на всички думи в Σ на азбука, включително празна дума епсилон).

На снимачната площадка на конфигурации, ще се въведе съотношението на преход в една стъпка: A

(Q, W) `A ( Q ', W) w = AW ", Φ (Q , а) = Q".

Ако W = ε, тогава ние, определен за всеки р Q: (Q, ε) ├ A (Q, ε).

през означаваме рефлексивен и преходен затварянето.

Неформално, (Q, W) (Q ', w ") означава, че автомат, като се започва работа в държавната Q в думата w = w 1. , , w л след краен брой стъпки 0 ≤ K ≤ л прочете първите к символите на w и до състояние р ", и w '= w к 1. , , w л е непрочетено почивка на думата w

А DFA признава (приема приема) думата w, ако по някаква р F (р 0, W) (Q, ε), т.е. След обработка на думите W машини преходи до състояние на приемащия.

Език на L A, разпознаваем (допустим получил) автомат A, се състои от всички думи, които са признати от този автомат:

L A = {w | А признава W}.

А езикът е, разбира се автомат, ако той е признат от някои DFA.

От тази дефиниция, по-специално, следва, че ε L A Q 0 F. Един и същ език може да бъде признат от различни машини.

Машини A и B се нарича еквивалентен ако същите езици, признати от тях, т.е. L A = L B.

Определяне на разпознаване на реч и език може лесно да бъде преведена на езика на диаграми.

Лема 1. автомат А признава (приема приема) думата w, ако по някаква р F на фигура D А има път от р 0 до Q, която носи думата w, т.е. w отнема р 0 в крайното състояние Q.

Това може да се докаже чрез индукция на дължината на думата w

По този начин, на езика на L A, призната от автомат A, се състои от всички думи, които се превръщат в неговата диаграма D A първоначалното състояние р 0 в крайното състояние на Е.

В много случаи е възможно да се покаже, че езикът L разбира картечен пистолет, изградени директно признава неговата машина. За да направите това, се опитват да разбият набор от входни думи в краен брой хомогенни класове на еквивалентни думи, т.е. думи, получаването на които е на входа на същия ефект върху възможността за продължаване на думи разпознаваем език. След това, за всеки един от класа, за да се създаде държавна машина и определяне на преходите между тези държави. Често това е полезно да се разграничат една държава, да представляват фалшиви думи, за които нито те, нито който и да е от разширения им не са част от езика.





; Дата: 05.01.2014; ; Прегледи: 278; Нарушаването на авторските права? ;


Ние ценим Вашето мнение! Беше ли полезна публикуван материал? Да | не



ТЪРСЕНЕ:


Вижте също:



zdes-stroika.ru - Studopediya (2013 - 2017) на година. Тя не е автор на материали, и дава на студентите с безплатно образование и използва! Най-новото допълнение , Al IP: 66.102.9.24
Page генерирана за: 0.047 сек.