Studopediya

КАТЕГОРИИ:


Астрономия- (809) Биология- (7483) Биотехнологии- (1457) Военное дело- (14632) Высокие технологии- (1363) География- (913) Геология- (1438) Государство- (451) Демография- (1065) Дом- (47672) Журналистика и СМИ- (912) Изобретательство- (14524) Иностранные языки- (4268) Информатика- (17799) Искусство- (1338) История- (13644) Компьютеры- (11121) Косметика- (55) Кулинария- (373) Культура- (8427) Лингвистика- (374) Литература- (1642) Маркетинг- (23702) Математика- (16968) Машиностроение- (1700) Медицина- (12668) Менеджмент- (24684) Механика- (15423) Науковедение- (506) Образование- (11852) Охрана труда- (3308) Педагогика- (5571) П Arhitektura- (3434) Astronomiya- (809) Biologiya- (7483) Biotehnologii- (1457) Военно дело (14632) Висока технологиите (1363) Geografiya- (913) Geologiya- (1438) на държавата (451) Demografiya- ( 1065) Къщи- (47672) журналистика и SMI- (912) Izobretatelstvo- (14524) на външните >(4268) Informatika- (17799) Iskusstvo- (1338) История- (13644) Компютри- (11121) Kosmetika- (55) Kulinariya- (373) култура (8427) Lingvistika- (374) Literatura- (1642) маркетинг-(23,702) Matematika- (16,968) инженерно (1700) медицина-(12,668) Management- (24,684) Mehanika- (15423) Naukovedenie- (506) образование-(11,852) защита truda- (3308) Pedagogika- (5571) п Политика- (7869) Право- (5454) Приборостроение- (1369) Программирование- (2801) Производство- (97182) Промышленность- (8706) Психология- (18388) Религия- (3217) Связь- (10668) Сельское хозяйство- (299) Социология- (6455) Спорт- (42831) Строительство- (4793) Торговля- (5050) Транспорт- (2929) Туризм- (1568) Физика- (3942) Философия- (17015) Финансы- (26596) Химия- (22929) Экология- (12095) Экономика- (9961) Электроника- (8441) Электротехника- (4623) Энергетика- (12629) Юриспруденция- (1492) Ядерная техника- (1748) oligrafiya- (1312) Politika- (7869) Лево- (5454) Priborostroenie- (1369) Programmirovanie- (2801) производствено (97182) от промишлеността (8706) Psihologiya- (18,388) Religiya- (3217) с комуникацията (10668) Agriculture- (299) Sotsiologiya- (6455) спортно-(42,831) Изграждане, (4793) Torgovlya- (5050) превозът (2929) Turizm- (1568) физик (3942) Filosofiya- (17015) Finansy- (26596 ) химия (22929) Ekologiya- (12095) Ekonomika- (9961) Telephones- (8441) Elektrotehnika- (4623) Мощност инженерно (12629) Yurisprudentsiya- (1492) ядрена technics- (1748)

Разгъване надолу автомати (мегапиксела-автоматична)




Помислете за концепцията за разгъване надолу автомати - тип резолвера, който е естествен модел ПАРСЕРИ контекстно-свободни езици. Разгъване надолу автомат - еднопосочен неопределящо разпознаване, в потенциално безкрайна памет, чиято информация предмети се съхраняват и използват по същия начин, както на касетите в магазин автоматични оръжия, т.е. при всеки наличен момент само съхранява горния елемент. Дискриминатора от този тип е показано по-долу.

Ще представлява един магазин (или списък магазин или търговски лента) под формата на символен низ, а горната част на магазина, ние приемаме най-левия или десния символ низ в зависимост от това, което е по-удобно в дадена ситуация. Докато ние приемаме, горната най-лявата поредица от букви, представляващи списъка списание.

Фиг. 1. разгъване надолу автомати

Определение: разгъване надолу автомати (за PDA) - е наредил седем вида

,

където

ограничен набор от състояния на автомата;

е краен вход азбука;

е ограничен азбука на стека символи;

набор от функции на преходите на машината (показване на набори от формата в комплекта на крайните подгрупи );

е първоначалното състояние на машината или устройството за управление ( );

е първоначалната символ на магазина (характер в магазина в началния път );

снимачната площадка на крайните състояния на автомата ( ).

Определение: Конфигурацията на разгъване надолу автомати (на PDA) е подредена тройна на формата

,

където

-CURRENT състояние на автомата;

Неразгледана -neispolzovannaya или част от входния низ (първата или лявата символ разположен над главата за четене), ако , Низ вход е било прочетено;

-soderzhimoe магазин (приемаме, че най-лявата поредица от букви, - е на върха на стека), ако е , Магазинът се счита за празна.

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

,

че е преход от една конфигурация в друга

,

ако където , , , , ,

индекс срещу писмена форма за идентификация, към която принадлежи даден машина двоичен връзка.

Споразумение: Next ще се смята за еквивалентни наименования - нула низ и - празен символ

Определение: Ако Това съотношение показва, че PDA Ние сме в състояние да и като като токов вход символ, разположен над главата на входа, и - като най-магазин характер може да се премести в ново състояние , Преместване на входния главата една клетка надясно и да се замени горния символ верига магазини стека символи. Това съотношение се нарича не е празна работа такт на PDA.



ако , Най-горният символ е отстранен от списанието, и по този начин намалява списък списание.

Определение: Ако Тогава вход символ на веригата не може да се прочете, но машината може да отидете в друга държава и да променят съдържанието на магазина, тези цикли се наричат -taktami.

машина работа приключва, ако магазинът е празен.

Определение: първоначалната конфигурация на машината ще се нарича тройна на формата

,

където

- първоначалното състояние ( );

- въвеждане на низ ( );

- магазин старт символ ( ).

Определение: Крайният конфигурация на машината ще се нарича тройна на формата

,

където

, , -Let символ.

Определение: Chain Тя позволява на PDA Ако има двоичен отношение на формата

(1)

където

- последователността на работа на цикъла на машината;

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

, , , ,

Определение: език се определя (или е разрешен) автоматично (означен ) Е набор от низове Разрешена пистолет , т.е.

например:

Изграждане на PDA, като се има предвид следния набор

;

,

решение:

Машина ще изглежда по следния начин:

Ние изграждане на функциите преход за машината MP (интуитивен начин)

;

;

;

;

;

,

Домашна работа: Напишете поредица от цикли MP-машина за двете изходни поредици

;

,

Домашни: Напишете други функции се движат на PDA (интуитивен метод), тоест, напишете вашето MP машина.

например:

Изграждане на PDA, като се има предвид следния набор

;

;

и за изграждане на поредица от цикли на работа на PDA за веригата

,

решение:

Ние изграждане на функциите преход за машината MP (интуитивен начин)

;

;

;

;

;

,

където

, , , ,

Сега ние се изгради поредица от мерки за работа машина за верига

,

,

Определение: Advanced MP-автоматично повикване седем вида

,

където

- крайно множество от състояния на автомата;

- окончателното допустимо въвеждане азбука;

- азбука на стека символи;

- картографиране на в комплекта на крайните подгрупи ;

- първоначалното състояние ( );

- старт символ магазин (характер в магазина в началния път );

- набор от крайни състояния ( ).

Определение: Конфигурация удължи PDA - е подредена тройка от формата

,

Определение: Първоначалната конфигурация удължи PDA ще призове трите вида

,

където

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

- въвеждане на низ;

- старт символ магазин.

Определение: Последната конфигурация удължи PDA ще призове трите вида

,

където

, , -Let символ.

Определение: Chain Тя позволява на напредналите MP-пистолет Ако има двоичен отношение на формата

,

където

- последователността на цикъла на работа удължи PDA ;

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

, , , , ,

Определение: език, който определя напреднали MP-пистолет Това е набор от формата

,

Забележка: Имайте предвид, че за разлика от конвенционалната автоматична MP-MP напреднали машина има възможност да продължи да работи, дори когато в магазина е празен.

например:

Construct продължителен MP-автоматична, следва предварително определена група от

и за изграждане на поредица от цикли на работа довърши PDA за веригата

,

решение:

Ето два начина за решаване на този пример.

Вариант №1.

Разширено MP машина ще изглежда така

граматични правила са както следва

,

Ние изграждане на функциите на преход за напреднали MP-машина (интуитивен метод)

,

,

,

,

,

,

Сега ние се изгради поредица от мерки за работа машина за верига

,

Последователността на цикъла на работа удължава MP-машина има формата

,

Вариант №2.

Разширено MP машина ще изглежда така

граматични правила са както следва

,

Ние изграждане на функциите на преход за напреднали MP-машина (интуитивен метод)

,

,

,

,

,

Сега ние се изгради поредица от цикли на работа удължи PDA за веригата

,

Последователността на мерки за работа удължи PDA има формата





; Дата на добавяне: 07.01.2014; ; Прегледи: 581; Нарушаването на авторски права? ;


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



ТЪРСЕНЕ:


Вижте също:



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