Сканы теоретического минимума (1131606), страница 2
Текст из файла (страница 2)
,36. Определение детерминированного МП автомата Детерменированный МП автомат определяется так же, как недетерминированный автомат, кроме того, должны выполняться условия: ° Множество Р(д,а,Е) содержит не более одного элемента для любых д ~ Я,а б Т > >' (е) > фЕ Г, ° ° Если Р(д, е, Я) ф 9, то Р(д, а, Е) = 9 для всех а Е Т 37. Определение конфигурации МП автомата Конфигурацией автомата с магазинной памятью (МП автомата) называется тройка (о,ю,и), где ° д б Д вЂ” текущее состояние магазинного устройства, ° и б Т' — непрочитанная часть входной цепочки; первый символ цепочки ш находится под входной головкой; если и> = е, то считается, что входная лента прочитана, ° и е Г' — содержимое магазина; самый левый символ цепочки и считается вершиной магазина; если и = е, то магазин считается пустым.
38. Определение языка, допускаемого МП автоматом Цепочка м допускается МП автоматом, если (уе, ы, Яе) )-' (д, е, и) для некоторых д ~ Р и и ® Язык, допускаемый МП-автоматом М вЂ” множество всех цепочек, допускаемых автоматом М. 39. Что означает, что недетерминированный МП автомат допускает опустошением магазина Цепочка ш допускается МП автоматом, если (де, ю, Ео) 1-' (д, е, е) для некоторого йч~"~ф В таком случае говорят, что автомат допускает цепочку опустошением магазнйа.' 40. Соотношение, между языками, порождаемыми КС-грамматиками, и языками, допускаемыми недетерминированными МП автоматами.
Язык является контекстно-свободным тогда и только тогда, когда он допускается магазинным автома том. 41. Формулировка леммы о разрастании для КС-языков Для любого контекстно-свободного языка 1~~, й: а ~ Х,, ~а~ > 1, а = иошху (а) ~нюх~ < Й, (Ъ) их ф е, (с) ии'юх'у Е Х,%. Определение нормальйой формы Хомского для КС-грамматики * Грамматика находится в нормальной форме Хомского, если правила вывода имеют вид: ° А -+ ВС; В, С Е ХУ, ° А — +а, ° ~ -+ е(е ~ .5; Я не входит ни в одну правую часть). 43. Определение правостороннего вывода в КС-'грамматике Вывод, в котором в любой сентенциальной форме на каждом шаге делается подстановка самого правого иетерминала, называется правосторонним.
Определение левостороннего вывода в КС-грамматике Вывод, в котором в любой сеитенцивльной форме на каждом шаге делается подстановка самого левого нетерминвла, называется левостороиним. Какая грамматика называется леворекурсивнойХ Грамматика называется леворекурсивной, если в ией имеется нетерминал А такой, что существует вывод А =~ Аи для некоторой строки и. Определение множества Р18 БТ1 Р18ЯТ(а) — множество терминалов, с которых начинаются строки, выводимые из а.
Определение множества РОЬЬОЖ1 РОЬЬОЧ~(А) — множество терминалов а, которые могут появиться непосредственно справа от А в некоторой сентенциальиой форме грамматики. 48. Определение ЬЬ(1) Грамматики Грамматики, для которых таблица предсказывающего анализатора ие имеет неоднозначно определенных входов, называются 1 Ь(1)- грамматиками.
49. Определение ЬН.(1) ситуации ЬВ,(1)-ситуацией называется пара (А -+ о.,8 а) где А — + р"— „где — + о — правило грамматики, а — терминал или правый концевой маркер 3. Вторая компо е аванцепочкой. н нта ситуации называется 50. Определение 1 Щ1) грамматики Если для КС-грамматики С функция Ас11оп не содержит неоднозначно определенных входов, то грамматика называется 1 Щ1)-грамматикой. 51. Какого типа конфликты могут появиться в канон ическо системе множеств й Ьв,(1) ситуаций? ° сдвиг/свертка — зная содержимое магазина и входной сим вол, не может решить, делаить ли сдвиг или свертку.
° свертка/свертка — не может решить, какую из нескольких сверток применить. 52. Определение конфигурации Ь11-анализатора Конфигурация Ьп, анализатора — пара, первая компонента которой — содержимое стека, вторая — непросмотренный вход: (ЯоХ1Я1ХгЯг "Х,~Я,~А А+1 "А 3) Эта конфигурация соответствует правой сентенпиальной форме Х Х ...Х А А; г .
1 +1..А„ 53. Как меняется конфигурация Ь11-анализатора при действии гес1псе? Пусть Ьй.(1)-анализатор находится в конфигурации (ЯоХ1Я1ХгЯг" Х Я, а;а;+г...а„3) Если Ассов (Я а| = д ',А 1 гедпсе А ~ у то анализатор выполняет свертку переходя в конфигурацию (ЯоХ1Я1ХгЯг" Х вЂ” тЯ вЂ” тАЯ, а;а;+ь..а„3) где Я = Соево [Я „, А1, г — длина 7, правой части вывода. 54. Какие типы действий выполняет ЬИ.-анализатор? Анализатор выполняет ° е1пй Я (сдвиг), где Я вЂ” символ состояния, ° гедисе А — ~ у (свертка по состоянию грамматики А — ~ ?) ° ассер1, ° еггог.
55. Как меняется конфигурация ЬВ-анализатора при действии 1г'и? г Г сли Асйоп(Я,а;) = оба/1Я, то анализатор выполняет сдвиг, переходя в конфнгура цию (ЯоХг Я1ХгЯг ..Х~Я~а;Я, а;+ь ..а„3) й Я Т Таким образом, в магазин помещаются входной символ а; и символ состояния Я опрел с стояния, опредшфмый ""' ""(Я, а;~. Текущим входным символом становится а. оотг '" г+ь 5б. Что такое основа правой сентенциальной формы Подцепочка сентенциельной формы, которая может быть сопоставлена правой части некоторого правила вывода, свертка по которому к левой части ра правила соответствует одному шагу в обращении правостороннего вывода, называется основой цепочки.
.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
