Теоретический минимум 2009 (1131627)
Текст из файла
Конструирование Компиляторов,Теоретический минимум (2009)Материал из ESyr's Wiki.см. также ответы на вопросы теоретического минимума 2007 года, списокопределений.Содержание1 Определение грамматики2 Определение грамматик типа 0 по Хомскому3 Определение грамматик типа 1 (неукорачивающих) по Хомскому4 Определение детерминированной машины Тьюринга5 Определение недетерминированной машины Тьюринга6 Определение конфигурации машины Тьюринга7 Определение языка, допускаемого машиной Тьюринга8 Соотношение между языками, порождаемыми грамматиками типа 0 иязыками, допускаемыми машинами Тьюринга9 Объяснить разницу между недетерминированной и детерминированноймашиной Тьюринга10 Определение регулярного множества11 Определение регулярного выражения12 Определение праволинейной грамматики13 Определение недетерминированного конечного автомата14 Определение детерминированного конечного автомата15 Объяснить разницу между недетерминированным и детерминированнымконечным автоматом16 Определение конфигурации конечного автомата17 Определение языка, допускаемого конечным автоматом18 Определение ε-замыкания для подмножества состояний НКА19 Определение расширенной функции переходов для КА20 Определение расширенной функции переходов для НКА21 Определение расширенной функции переходов для ДКА22 Определение функции firstpos для поддерева в дереве регулярноговыраженияСтр.
1 из 1523 Определение функции lastpos для поддерева в дереве регулярноговыражения24 Определение функции followpos для позиций в дереве регулярноговыражения25 Сформулировать соотношение между регулярными множествами иязыками, допускаемыми КА26 Определение регулярной грамматики27 Сформулировать соотношение между языками, порождаемымиправолинейными грамматиками и языками, допускаемыми КА28 Определение эквивалентных состояний ДКА29 Определение различимых состояний ДКА30 Определение контекстно-свободной грамматики без ε-правил31 Определение контекстно-свободной грамматики32 Определение выводимости в грамматике33 Определение языка, порождаемого КС-грамматикой34 Определение сентенциальной формы35 Определение однозначной КС-грамматики36 Определение неоднозначной КС-грамматики37 Определение недетерминированного МП автомата38 Определение детерминированного МП автомата39 Определение конфигурации МП автомата40 Определение языка, допускаемого МП автоматом41 Определение недетерминированного МП автомата, допускающегоопустошением магазина42 Соотношение, между языками, порождаемыми КС-грамматиками, иязыками, допускаемыми недетерминированными МП автоматами43 Формулировка леммы о разрастании для КС-языков44 Определение нормальной формы Хомского для КС-грамматики45 Определение правостороннего вывода в КС-грамматике46 Определение левостороннего вывода в КС-грамматике47 Что такое леворекурсивная грамматика?48 Определение множества FIRST149 Определение множества FOLLOW150 Определение LL(1) грамматики51 Определение LR(1) ситуации52 Определение LR(1) грамматики53 Какого типа конфликты могут появиться в канонической системе множествLR(1) ситуаций?54 Определение конфигурации LR-анализатора55 Как меняется конфигурация LR-анализатора при действии reduce?56 Какие типы действий выполняет LR-анализатор?Стр.
2 из 1557 Как меняется конфигурация LR-анализатора при действии shi ?58 Что такое основа правой сентенциальной формыОпределение грамматикиГрамматкиа G = (N,T,P,S) - четверка множеств, гдеN - алфавит нетерминальных символовT - алфавит терминальных символов, пересечение N и T = ∅P - множество правил вида α → β, α ∈ ( N ∪ T)*N(N ∪ T)*, β ∈ (N ∪ T)*S ∈ N - начальный символ или аксиома грамматикиОпределение грамматик типа 0 по ХомскомуЕсли на грамматику G = (N, T, P, S) не накладываются никакие ограничения, то еёназывают грамматикой типа 0, или грамматикой без ограничений.Определение грамматик типа 1 (неукорачивающих) поХомскомуЕсли1.
Каждое правило грамматики, кроме S → ε, имеет вид α → β, |α| ≤ |β|2. В том случае, когда S → ε ∈ P, символ S не встречается в правых частях правилто грамматику называют грамматикой типа 1, или неукорачивающей.Определение детерминированной машины ТьюрингаДетерминированная машина Тьюринга — Tm = (Q, Г, Σ, D, q0, F)Q — конечное множество состоянийГ — конечное множество ленточных символов (конечный алфавит), один изкоторых называется пустым и обозначается обычно bΣ — входной алфавит, Σ ⊆Г\{b} (b - пустой символ)D — правила переходаD: (Q\F) × Г → Q × Г × {L, R}q0 ∈ Q — начальное состояниеСтр.
3 из 15F ⊆Q — множество конечных состоянийОпределение недетерминированной машиныТьюрингаНедетерминированная машина Тьюринга — Tm = (Q, Г, Σ, D, q0, F)Q — конечное множество состоянийГ — конечное множество символов (конечный алфавит)Σ — входной алфавит, Σ ⊆Г\{b} (b - пустой символ)D — правила переходаD: (Q\F) × Г → 2Q × Г × {L, R}q0 ∈ Q — начальное состояниеF ⊆Q — множество конечных состоянийОпределение конфигурации машины ТьюрингаКонфигурацией машины Тьюринга называется тройка (q, w, i), гдеq ∈ Q — состояние машины Тьюрингаw ∈ Г* —текущее содержимое занятого участка ленты, w = a 1 … ani ∈ Z — положение головки машины ТьюрингаОпределение языка, допускаемого машиной ТьюрингаЯзык, допускаемый машиной Тьюринга — множество таких слов w, что, машинаТьюринга, находясь в состоянии (q0, w, 1) может достигнуть через конечное числопереходов состояния q ∈ F.Соотношение между языками, порождаемымиграмматиками типа 0 и языками, допускаемымимашинами ТьюрингаКласс языков, допускаемых машиной Тьюринга, эквивалентен классу языков,порождаемых грамматиками типа 0.Объяснить разницу между недетерминированной иСтр.
4 из 15детерминированной машиной ТьюрингаДетерминированная машина Тьюринга из данного состояния по данному символуможет сделать не более одного перехода, недетерминированная же такимсвойством не обладает.Определение регулярного множестваРегулярное множество в алфавите T определяется следующим образом:{} (пустое множество) — регулярное множество в алфавите T{a} — регулярное множество в алфавите T для каждого a ∈ T{ε} — регулярное множество в алфавите TЕсли P и Q — регулярные множества в алфавите T, то таковы же и множестваP ∪ Q (объединение)PQ (конкатенация, то есть множество таких pq, что p ∈ P, q ∈ Q)P* (итерация: P* = {ε} ∪ P ∪ PP ∪ PPP ∪ …)Ничто другое не является регулярным множеством в алфавите TОпределение регулярного выраженияРегулярное выражение — форма записи регулярного множества.Регулярное выражение и обозначаемое им регулярное множество определяютсяследующим образом:∅ — обозначает множество {}ε — обозначает множество {ε}a — обозначает множество {a}Если РВ p и q обозначают множества P и Q соответственно, то:(p|q) обозначает P ∪ Qpq обозначает PQ(p*) обозначет P*Ничто другое не является регулярным выражением в данном алфавитеОпределение праволинейной грамматикиПраволинейная грамматика или грамматика типа 3 по Хомскому — грамматика видаA → w, A → wB, w ∈ T*.Стр.
5 из 15Определение недетерминированного конечногоавтоматаНедетерминированный конечный автомат - M = (Q, Σ, D, q0, F)Q — конечное непустое множество состоянийΣ — входной алфавитD — правила переходаQ × ( Σ ∪ {ε} ) → 2Qq0 ∈ Q — начальное состояниеF ⊆Q — множество конечных состоянийОпределение детерминированного конечного автоматаДетерминированный конечный автомат - M = (Q, Σ, D, q0, F)Q — конечное непустое множество состоянийΣ — конечный входной алфавитD — правила переходаQ×Σ→Qq0 ∈ Q — начальное состояниеF ⊆Q — множество конечных состоянийОбъяснить разницу между недетерминированным идетерминированным конечным автоматомНедетерминированный конечный автомат является обобщениемдетерминированного.
Существует теорема, гласящая, что «Любойнедетерминированный конечный автомат может быть преобразован вдетерминированный так, чтобы их языки совпадали» (такие автоматы называютсяэквивалентными).Определение конфигурации конечного автоматаПусть M = (Q, T, D, q0, F) — НКА. Конфигурацией автомата M называется пара (q,ω) ∈ Q × T*, где q — текущее состояние управляющего устройства, а ω — цепочкасимволов на входной ленте, состоящая из символов под головкой и всех символовсправа от неё.Стр. 6 из 15Определение языка, допускаемого конечнымавтоматомАвтомат M допускает цепочку ω, если (q0, ω) * (q, ε) для некоторого q ∈ F.
Языком,допускаемым автоматом M, называется множество входных цепочек,допускаемыхавтоматом M. То есть:L(M) = {ω | ω ∈ T* и (q0, ω) * (q, ε) для некоторого q ∈ F}Определение ε-замыкания для подмножествасостояний НКАε-замыкание множества состояний R, R ⊆Q — множество состояний НКА,достижимых из состояний, входящих в R, посредством только переходов по ε, то естьмножествоS=q ∈ R {p | (q, ε) * (p, ε)}Определение расширенной функции переходов для КАРасширенная функция переходов множества состояний R, R ⊆Q по a — множествосостояний НКА, в которые есть переход на входе a для состояний из R, то естьмножествоS=q ∈ R {p | p ∈ D(q, a)}Определение расширенной функции переходов дляНКАОпределение расширенной функции переходов дляДКАОпределение функции firstpos для поддерева в дереверегулярного выраженияФункция firstpos(n) для каждого узла n узла синтаксического дерева регулярныхСтр.
7 из 15выражений даёт множество позиций, которые соответствуют первым символам вцепочках, генерируемых подвыражением с вершиной n. Построение:узел nfirstpos(n)i≠ε∅{i}u|vfirstpos(u) ∪ firstpos(v)u.vv*if nullable(u) then firstpos(u) ∪ firstpos(v) else firstpos(u)firstpos(v)εОпределение функции lastpos для поддерева в дереверегулярного выраженияФункция lastpos(n) для каждого узла n узла синтаксического дерева регулярныхвыражений даёт множество позиций, которым соответствуют последние символы вцепочках, генерируемых подвыражениями с вершиной n. Построение lastpos(n):узел nε∅lastpos(n)i≠ε{i}u|vlastpos(u) ∪ lastpos(v)u.vif nullable(v) then lastpos(u) ∪ lastpos(v) else lastpos(v)lastpos(v)v*Определение функции followpos для позиций в дереверегулярного выраженияФункция followpos(i) для позиции i есть множество позиций j таких, что существуетнекоторая строка …cd…, входящая в язык, описываемый регулярным выражением,такая, что позиция i соответствует вхождению c, а позиция j — вхождению d.Сформулировать соотношение между регулярнымимножествами и языками, допускаемыми КАЛюбой конечный автомат распознает регулярное множество цепочек символоввходного алфавита.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
