Teormin (2009) (796974)

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

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

Конструирование Компиляторов, Теоретический минимум (2009)1. Определение грамматик типа 0 по ХомскомуЕсли на грамматику G = (N, T, P, S) не накладываются никакие ограничения, то её называют грамматикой типа 0, илиграмматикой без ограничений.2. Определение грамматик типа 1 (неукорачивающих) по ХомскомуЕсли1.Каждое правило грамматики, кроме S → ε, имеет вид α → β, |α| ≤ |β|2.В том случае, когда S → ε ‫ א‬P, символ S не встречается в правых частях правилто грамматику называют грамматикой типа 1, или неукорачивающей.3. Определение детерминированной машины ТьюрингаTm = (Q, Г, Σ, D, q0, F) , гдеQ — конечное множество состоянийГ — конечное множество символов (конечный алфавит)Σ — входной алфавит, Σ ‫ ك‬Г\{b} (b - пустой символ)D — правила переходаD: (Q\F) × Г → Q × Г × {L, R}q0 ‫ א‬Q — начальное состояниеF ‫ ك‬Q — множество конечных состояний4.

Определение недетерминированной машины ТьюрингаTm = (Q, Г, Σ, D, q0, F) , гдеQ — конечное множество состоянийГ — конечное множество символов (конечный алфавит)Σ — входной алфавит, Σ ‫ ك‬Г\{b} (b - пустой символ)D — правила переходаD: (Q\F) × Г → в множество подмножеств множества Q × Г × {L, R}q0 ‫ א‬Q — начальное состояниеF ‫ ك‬Q — множество конечных состояний5. Определение конфигурации машины ТьюрингаКонфигурацией машины Тьюринга называется тройка (q, w, i), гдеq ‫ א‬Q — состояние машины Тьюрингаw ‫ א‬Г* — вход, помещаемый на ленту машины Тьюрингаi ‫ א‬Z — положение головки машины Тьюринга6.

Определение языка, допускаемого машиной ТьюрингаЯзык, допускаемый машиной Тьюринга — множество таких слов w, что, машина Тьюринга, находясь в состоянии (q0, w, 1)может достигнуть через конечное число переходов состояния q ‫ א‬F.7. Соотношение между языками, порождаемыми грамматиками типа 0 и языками, допускаемыми МТ.Класс языков, допускаемых машиной Тьюринга, эквивалентен классу языков, порождаемых грамматиками типа 0.8. Объяснить разницу между недетерминированной и детерминированной машиной ТьюрингаДетерминированная машина Тьюринга из данного состояния по данному символу может сделать не более одногоперехода, недетерминированная же таким свойством не обладает.9.

Определение регулярного множестваРегулярное множество в алфавите T определяется следующим образом:1. {} (пустое множество) — регулярное множество в алфавите T2. {a} — регулярное множество в алфавите T для каждого a ‫ א‬T3. {ε} — регулярное множество в алфавите T4. Если P и Q — регулярные множества в алфавите T, то таковы же и множестваa. P ‫ ׫‬Q (объединение)b. PQ (конкатенация, то есть множество таких pq, что p ‫ א‬P, q ‫ א‬Q)c. P* (итерация: P* = {ε} ‫ ׫‬P ‫ ׫‬PP ‫ ׫‬PPP ‫)… ׫‬5. Ничто другое не является регулярным множеством в алфавите T10.

Определение регулярного выраженияРегулярное выражение и обозначаемое им регулярное множество определяются следующим образом:1. ‫ — ׎‬обозначает множество {}2. ε — обозначает множество {ε}3. a — обозначает множество {a}4. Если РВ p и q обозначают множества P и Q соответственно, то:a. (p|q) обозначает P ‫ ׫‬Qb. pq обозначает PQc. (p*) обозначает P*5. Ничто другое не является регулярным выражением в данном алфавите11. Определение праволинейной грамматикиЕсли каждое правило грамматики имеет вид либо A → w, либо A → wB, где w ‫ א‬T*, А ‫ א‬N, то ее называют праволинейнойграмматикой или грамматикой типа 3 по Хомскому.25.

Сформулировать соотношение между языками, порождаемыми праволинейными грамматиками иязыками, допускаемыми КАДля каждой праволинейной грамматики G существует конечный автомат M такой, что L(M)=L(G).Для каждого конечного автомата M существует праволинейная грамматика G такая, что L(G)=L(M).26. Определение эквивалентных состояний ДКАДва различных состояния q и q′ в конечном автомате M = (Q, T , F , H , Z ) называются n-эквивалентными, n‫א‬N‫{׫‬0}, если,находясь в одном их этих состояний и получив на вход любую цепочку символов ω: ω ‫ א‬T*, |ω|≤n, автомат может перейтив одно и то же множество конечных состояний.Состояния эквиваленты, если n = ∞.27.

Определение различимых состояний ДКАДва различных состояния q и q’ называются различимыми, если существует цепочка такая, что при ее разборе одно изэтих состояний переход в конечное, а другое нет.28. Определение контекстно-свободной грамматики без е-правилГрамматика называется контекстно-свободной без е-правил, если:1) Если каждое правило грамматики имеет вид A → α, где A ‫ א‬N, α ‫( א‬N ‫ ׫‬T)+2) Допускается S → ߝ, если S не входит ни в какую правую часть29. Определение контекстно-свободной грамматикиЕсли каждое правило грамматики имеет вид A → α, где A ‫ א‬N, α ‫( א‬N ‫ ׫‬T)*, то ее называют контекстно-свободной.30.

Определение вывода в КС-грамматикеОпределим на множестве (N ‫ ׫‬T)* грамматики G = (N, T, P, S) бинарное отношение выводимости «֜» следующим образом:если δ → γ ‫ א‬P, то αδβ ֜ αγβ для всех α, β ‫( א‬N ‫ ׫‬T)*. Если α1 ֜ α2, то α2 непосредственно выводима из α1.Если α ֜k β (k ≥ 0), то существует последовательность шагов γ0 ֜ γ1 ֜ γ2 ֜ … ֜ γk − 1 ֜ γk, где α = γ0 и β = γk.Последовательность цепочек γ0, γ1, γ2, …, γk − 1, γk в этом случае называется выводом β из α.31. Определение языка, порождаемого КС-грамматикойЯзыком, порождаемым грамматикой G = (N, T, P, S) (обозначается L(G)) называется множество всех цепочек терминалов,выводимых из аксиомы, то есть: L(G) = {w | w ‫ א‬T*, S ֜+ w}32.

Определение сентенциальной формыСентенциальная форма — последовательность символов (терминалов и нетерминалов), выводимых из аксиомы.33. Определение однозначной КС-грамматикиУпорядоченное помеченное дерево D называется деревом вывода цепочки ω КС-грамматике G=(N,T,P,S), если выполненыследующие условия:1) корень дерева D помечен S2) каждый лист помечен либо a ‫ א‬T, либо ߝ3) каждый внутренняя вершина помечена нетерминалом A ‫ א‬N.4) если X – нетерминал, которым помечена внутренняя вершина и X1,…Xn – метки ее прямых потомков в указанномпорядке, то X → X1,…Xn – правило из множества P.5) Цепочка, составленная из выписанных слева направо меток листьев, равна w.КС грамматика называется однозначной или детерминированной, если всякая выводимая терминальная цепочка имееттолько одно дерево вывода.34. Определение неоднозначной КС-грамматикиКС-грамматика G называется неоднозначной, если существует хотя бы одна цепочка α ‫ ؿ‬L(G), для которой может бытьпостроено два или более различных деревьев вывода.35.

Определение недетерминированного МП автоматаНедетерминированный автомат с магазинной памятью (МП-автомат) — семёрка M = (Q, T, Г, D, q0, Z0, F), где1. Q — конечное множество состояний, представляющее всевозможные состояния управляющего устройства2. T — конечный входной алфавит3. Г — конечный алфавит магазинных символов4. D — отображение множества Q × (T ‫{ ׫‬ε}) × Г в множество всех конечных подмножеств Q × Г*, называемое функциейпереходов5. q0 ‫א‬Q — начальное состояние управляющего устройства6.

Z0 ‫א‬Г — символ, находящийся в магазине в начальный момент (начальный символ магазина)7. F ‫ك‬Q — множество заключительных состояний36. Определение детерминированного МП автоматаДетерминированный автомат с магазинной памятью (МП-автомат) — семёрка M = (Q, T, Г, D, q0, Z0, F), где1. Q — конечное множество состояний, представляющее всевозможные состояния управляющего устройства2. T — конечный входной алфавит3. Г — конечный алфавит магазинных символов4. D — отображение множества Q × (T ‫{ ׫‬ε}) × Г в множество всех конечных подмножеств Q × Г*, называемое функциейпереходов5.

q0 ‫ א‬Q — начальное состояние управляющего устройства6. Z0 ‫ א‬Г — символ, находящийся в магазине в начальный момент (начальный символ магазина)7. F ‫ ك‬Q — множество заключительных состоянийКроме того, должны выполняться следующие условия:1. Множество D(q, a, Z) содержит не более одного элемента для любых q ‫ א‬Q, a ‫ א‬T ‫{ ׫‬ε}, Z ‫ א‬Г2. Если D(q, ε, Z) ≠ ‫׎‬, то D(q, a, Z) = ‫ ׎‬для всех a ‫ א‬T12. Определение недетерминированного конечного автоматаM = (Q, Σ, D, q0, F) , гдеQ — конечное непустое множество состоянийΣ — конечное множество допустимых входных символов (входной алфавит)D — функция переходов, отображающая множество Q × ( Σ ‫{ ׫‬ε} ) во множество подмножеств множества Q, определяющаяповедение управляющего устройстваq0 ‫ א‬Q — начальное состояние управляющего устройстваF ‫ ك‬Q — множество заключительных состояний13.

Определение детерминированного конечного автоматаЭто НКА M = (Q, Σ, D, q0, F), гдеQ — конечное непустое множество состоянийΣ — конечное множество допустимых символов (входной алфавит)D — функция переходов, отображающая множество Q × ( Σ ‫{ ׫‬ε} ) во множество подмножеств множества Q, определяющаяповедение управляющего устройстваq0 ‫ א‬Q — начальное состояниеF ‫ ك‬Q — множество конечных состояний,для которого выполнены следующие условия:1) D(q,e) = Ø для любого q ‫ א‬Q2) D(q,a) содержит не более одного элемента для любых q ‫ א‬Q и a ‫ א‬Σ14.

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

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

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