Teormin (2009) (796974), страница 2

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

Текст из файла (страница 2)

Объяснить разницу между недетерминированным и детерминированным конечным автоматомДетерминированный автомат является частным случаем недетерминированного автомата, который на каждом тактеработы имеет возможность перейти не более чем в одно состояние и не может делать переходы по ߝ.15. Определение конфигурации конечного автоматаПусть M = (Q, T, D, q0, F) — НКА. Конфигурацией автомата M называется пара (q, ω) ‫ א‬Q × T*, где q — текущее состояниеуправляющего устройства, а ω — цепочка символов на входной ленте, состоящая из символов под головкой и всехсимволов справа от неё.16.

Определение языка, допускаемого конечным автоматомТактом автомата M называется бинарное отношение ٥ , определенное на конфигурациях M следующим образом: если p ‫א‬D(q,a), где a ‫ א‬T‫{׫‬ε}, то (q, aw) ٥ (p, w) для всех w ‫ א‬T*.Автомат M допускает цепочку ω, если (q0, ω) ٥* (q, ε) для некоторого q ‫ א‬F.Языком, допускаемым автоматом M, называется множество входных цепочек, допускаемых автоматом M.То есть: L(M) = {ω | ω ‫ א‬T* и (q0, ω) ٥* (q, ε) для некоторого q ‫ א‬F}17. Определение ε-замыкания для подмножества состояний НКАε-замыкание (ε-closure) множества состояний R, R ‫ ك‬Q — множество состояний НКА, достижимых из состояний, входящихв R, посредством только переходов по ε, то есть множество S = ‫א“ڂ‬ሼ’ȁሺ“ǡ ɂሻ ٟ‫ כ‬ሺ’ǡ ɂሻሽ18.

Определение расширенной функции переходов для ДКАОбозначим De – как расширенную функцию перехода для ДКА M=(Q, Σ, D, q0, F). Тогда:1) De(q, a) ‫ ؠ‬D(q, a), a ‫ א‬T, q ‫ א‬Q2) De(q, wa) ‫ ؠ‬D(De(q, w), a), a ‫ א‬T, w ‫ א‬T+, q ‫ א‬Q19. Определение расширенной функции переходов для НКАОбозначим De – как расширенную функцию перехода для НКА M=(Q, Σ, D, q0, F).

Тогда:1) De(q, ߝ) = ߝ െ ݈ܿ‫{(݁ݎݑݏ݋‬q}), q ‫ א‬Q2) De(q, a) = {p1, p2, … , pk}, pi ‫ א‬D(q,a) ‫׊‬i=1..k, q ‫ א‬Q, a ‫ א‬T3) De(q, wa) = ߝ െ ݈ܿ‫ ݅ڂ (݁ݎݑݏ݋‬ሺ’‹ǡ ƒሻ ), pi = De(q, w), w ‫ א‬T+, q ‫ א‬Q20. Определение функции firstpos для поддерева в дереве регулярного выраженияФункция firstpos(n) для каждого узла n узла синтаксического дерева регулярных выражений даёт множество позиций,которые соответствуют первым символам в цепочках, генерируемых подвыражением с вершиной n.21.

Определение функции lastpos для поддерева в дереве регулярного выраженияФункция lastpos(n) для каждого узла n узла синтаксического дерева регулярных выражений даёт множество позиций,которым соответствуют последние символы в цепочках, генерируемых подвыражениями с вершиной n.22. Определение функции followpos для позиций в дереве регулярного выраженияФункция followpos(i) для позиции i есть множество позиций j таких, что существует некоторая строка …cd…, входящая вязык, описываемый регулярным выражением, такая, что позиция i соответствует вхождению c, а позиция j — вхождениюd.23. Сформулировать соотношение между регулярными множествами и языками, допускаемыми КА1) Для всякого регулярного множества имеется КА, допускающий в точности это регулярное множество.2) Язык, допускаемый конечным автоматом, есть регулярное множество.24.

Определение регулярной грамматикиПраволинейная грамматика G=(N,T,P,S) называется праволинейной регулярной, если:1) каждое ее правило, кроме S՜ ߝ, имеет вид либо A → w, либо A → wB, w ‫ א‬T, A,B‫א‬N2) в том случае, когда S՜ ߝ ‫ א‬P, начальный символ S не встречается в правых частях правил.Леволинейная грамматика G=(N,T,P,S) называется леволинейной регулярной, если:1) каждое ее правило, кроме S՜ ߝ, имеет вид либо A → w, либо A → Bw, w ‫ א‬T, A,B‫א‬N2) в том случае, когда S՜ ߝ ‫ א‬P, начальный символ S не встречается в правых частях правил.Регулярные грамматики — праволинейные или леволинейные регулярные грамматики.37.

Определение конфигурации МП автоматаКонфигурацией автомата с магазинной памятью (МП автомата) называется тройка (q, w, u), гдеq ‫ א‬Q — текущее состояние магазинного устройстваw ‫ א‬T* — непрочитанная часть входной цепочки; первый символ цепочки w находится под входной головкой; если w = ε,то считается, что входная лента прочитанаu ‫ א‬Г* — содержимое магазина; самый левый символ цепочки u считается вершиной магазина; если u = ε, то магазинсчитается пустым38.

Определение языка, допускаемого МП автоматомЦепочка w допускается МП автоматом M = (Q, T, Г, D, q0, Z0, F), если (q0, w, Z0)ٟ* (q, ε, u) для некоторых q ‫ א‬F и u ‫ א‬Г*.Язык, допускаемый МП-автоматом M — множество всех цепочек, допускаемых автоматом M.39. Что означает то, что недетерминированный МП автомат допускает опустошением магазинаЦепочка w допускается МП автоматом, если (q0, w, Z0)ٟ* (q, ε, ε) для некоторого q ‫ א‬Q. В таком случае говорят, что автоматдопускает цепочку опустошением магазина.40.

Соотношение, между языками, порождаемыми КС-грамматиками, и языками, допускаемыминедетерминированными МП автоматамиЯзык является КС тогда и только тогда, когда он допускается магазинным автоматом.41. Формулировка леммы о разрастании для КС-языковДля любого контекстно-свободного языка L ‫ ׌‬l: ‫ ׊‬α ‫ א‬L, |α| ≥ l, α = xyz1. |xy| ≤ l2. |y| > 03.

xyiz ‫ א‬L, ‫ ׊‬i ≥ 042. Определение нормальной формы Хомского для КС-грамматикиГрамматика находится в нормальной форме Хомского, если правила вывода имеют вид:· A → BC; где B, C ‫ א‬N· A→a· S → ε (если ε ‫ א‬L; S не входит ни в одну правую часть)43. Определение правостороннего вывода в КС-грамматикеВывод, в котором в любой сентенциальной форме на каждом шаге делается подстановка самого правого нетерминала,называется правосторонним.44. Определение левостороннего вывода в КС-грамматикиВывод, в котором в любой сентенциальной форме на каждом шаге делается подстановка самого левого нетерминала,называется левосторонним.45.

Какая грамматика называется леворекурсивной?Грамматика называется леворекурсивной, если в ней имеется нетерминал A такой, что существует вывод A ֜+ Au длянекоторой цепочки u.46. Определение множества FIRST1В1. FIRST1 — множество всех терминальных символов, с которых может начинаться цепочка терминальных символов,выводимых из цели грамматики или ε, если u ֜* ε.В2. Множество FIRST(A) — множество терминальных символов, которыми начинаются цепочки, выводимые из A вграмматике G = (VT, VN, P, S), то есть, FIRST(A) = {a ‫ א‬VT | A ֜ aα, A ‫ א‬VN, α ‫( א‬VT ‫ ׫‬VN)*}47. Определение множества FOLLOW1Пусть A — нетерминал.

Тогда FOLLOW(A) — множество терминалов a, которые могут появиться непосредственно справаот A в некоторой сентенциальной форме, то есть, множество терминалов a таких, что существует вывод вида S ֜* uAavдля некоторых u и v.48. Определение LL(1) ГрамматикиГрамматики, для которых таблица предсказывающего анализатора не имеет неоднозначно определенных входов,называются LL(1)-грамматиками.49. Определение LR(1) ситуацииLR(1)-ситуацией называется пара [A → α.β, a], где A → αβ — правило грамматики, a — терминал или правый концевоймаркер $.

Вторая компонента ситуации называется аванцепочкой.50. Определение LR(1) грамматикиВ1. Если для КС-грамматики G функция Action, полученная в результате работы алгоритма построения LR(1)-таблицы, несодержит неоднозначно определенных входов, то грамматика называется LR(1)-грамматикой.В2. Грамматика называется LR(1)-грамматикой, если из условий:1) S’ ֜r* uAw ֜ r uvw,2) S’ ֜ r * zBx ֜ r uvy,3) FIRST(w) = FIRST(y)cледует, что uAy = zBx (т.е. u=z, A=B, x=y).51.

Какого типа конфликты могут появиться в канонической системе множеств LR(1) ситуаций?Анализатор типа сдвиг-свертка при анализе некоторой цепочки может достигнуть конфигурации, в которой он, знаясодержимое магазина и следующий входной символ, не может решить:1) Делать ли сдвиг или свертку (конфликт сдвиг/свертка)2) Какую из нескольких сверток применить (конфликт свертка/свертка)52. Определение конфигурации LR-анализатораКонфигурация LR анализатора — пара, первая компонента которой —содержимое стека, вторая — непросмотренныйвход:(S0 X1 S1 X2 S2 … Xm Sm, ai ai + 1 … an $).Эта конфигурация соответствует правой сентенциальной форме X 1 X2 … Xm ai ai + 1 … an.53.

Как меняется конфигурация LR-анализатора при действии reduce?Если выполняется reduce A→µ, то анализатор выполняет свертку, переходя в конфигурацию(S0 X1 S1 X2 S2 … Xm-r Sm-rAS, ai ai + 1 … an $), где S = Goto[Sm-r,A] и r – длина µ, правой части вывода.Анализатор сначала удаляет из магазина r символов состояния и r символов грамматики, так что на верхушкеоказывается состояние Sm-r. Затем анализатор помещает в магазин A – левую часть правила вывода, и S – символсостояния, определяемый Goto[Sm-r,A]. На шаге свертки текущий входной символ не меняется.

Для LR(1)-анализаторов Xmr … Xm – последовательность символов грамматики, удаляемых из магазина, всегда соответствует µ - правой частиправила вывода, по которому делается свертка.54. Какие типы действий выполняет LR-анализатор?Анализатор выполняет 4 вида действий:1) Сдвиг2) Свертка3) Успешное завершение разбора4) Обнаружение ошибки55.

Как меняется конфигурация LR-анализатора при действии shift?Если выполняется shift S , то анализатор выполняет сдвиг, переходя в конфигурацию(S0 X1 S1 X2 S2 … Xm SmaiS, ai + 1 … an $).Таким образом, в магазин помещаются входной символ ai и символ состояния S, определяемый Action[Sm, ai]. Текущимвходным символом становится ai + 1.56.

Что такое основа правой сентенциальной формыПодцепочка сентенциальной формы, которая может быть сопоставлена правой части некоторого правила вывода,свертка по которому к левой части правила соответствует одному шагу в обращении правостороннего вывода,называется основой цепочки.Составители и редакторы: Кононов Алексей,Коляскина Екатерина, Кийко Александргруппа 328.Часть материалов взята с http://www.esyr.us2009 год..

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

Список файлов ответов (шпаргалок)