[11.04.11] Лекция №10 (1061985)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Лекция №10 [11.04.11]

Просто пример постройки чего-то:

возьмём так:

чтобы получить при :

чтобы :

чтобы :

а вот если ,

а : ещё выводы

А теперь МП-автомат:

- входной алфавит состоит из двух букв

в магазине надо запоминать количество букв и больше ничего:

состояния: , - стартовая, , это мы выяснили в процессе

команды:

, только если

, считаем буквы

, буквы закончились, начались и одну в стеке надо стереть

, теперь идём по , стирая из стека , пока они не закончатся

, ( ), автомат работу закончил

, а тут на случай, если

проверка:

а проверим с неправильным словом:

, а для данной конфигурации нет команды, недостижима финальная конфигурация

и ещё:

, тоже тупиковая конфигурация

Короче, мы экспериментально проверили, что наш КА допускает цепочки требуемого языка.

Построение МП-автомата по КС-грамматике

Для каждой КС-грамматики можно построить МП-автомат, распознаваемый соответствующим КС-языком.

система команд строится следующим образом:

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

и для добавляется команда

других команд нет

Пример:

приступим:

1)

2)

3)

это мы обработали грамматику по первому правилу

теперь для нетерминалов:

4)

5)

6)

и на этом построение грамматики закончено

проверим:

, принадлежит ли она

[можно любое из трёх, но кто его знает, получится ли]

значит, предъявленная цепочка переходов моделирует левый вывод цепочки в исходной грамматике:

таким образом, проблема в данном случае решилась очень просто – мы использовали магазин для имитации этого самого вывода.

Но единственный ли это способ построения автомата? Нет, конечно, в данном случае реализован только один из возможных способов построения МП-автомата по данной грамматике.

Давайте ещё пример:

Вернёмся в языку и построим для него МП-автомат по грамматике:

, , ,

множество правил:

1)

2)

3)

4)

Построение МП-автомата по грамматике представляет собой, в общем-то, только теоретический интерес и нужно только для доказательства того, что МП-автоматы эквивалентны КС-грамматикам и являются распознавателями для КС-языков. Имеет место и обратная теорема:

Для каждого МП-автомата можно построить эквивалентную ему КС-грамматику

Но как? Когда мы строили автомат по грамматике, всё было просто, было понятно, какие символы писать в магазин и что извлекать.

А теперь вот есть у нас МП-автомат, у него есть множество состояний, входной и выходной алфавиты, стартовое и заключительные состояния, и вот где здесь искать грамматику?

Ну, терминальный алфавит будет совпадать , но откуда брать нетерминалы? И где правила? И это вот основная проблема во всей этой теории.

Что такое команда МП-автомата?

- находимся в состоянии , читаем на ленте и в магазине лежит

- перешли в состояние и в магазин записали

Цель: находясь в состоянии и имея верхним символом магазина мы хотим перейти в некоторое состояние , тогда будет нетерминалом новой грамматики.

А правила новой грамматики будут иметь такой вид:

?

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов лекций