Теоретический минимум 2007

Конструирование Компиляторов,Теоретический минимум (2007)Материал из ESyr's Wiki.Содержание1 Определение грамматик типа 0 по Хомскому2 Определение грамматик типа 1 (неукорачивающих) по Хомскому3 Определение детерминированной машины Тьюринга4 Определение недетерминированной машины Тьюринга5 Определение конфигурации машины Тьюринга6 Определение языка, допускаемого машиной Тьюринга7 Соотношение между языками, порождаемыми грамматиками типа 0 иязыками, допускаемыми машинами Тьюринга8 Объяснить разницу между недетерминированной и детерминированноймашиной Тьюринга9 Определение линейно-ограниченного автомата10 Соотношение между языками, порождаемыми грамматиками типа 0 иязыками, допускаемыми линейно-ограниченными автоматами11 Определение регулярного множества12 Определение регулярного выражения13 Определение праволинейной грамматики14 Определение недетерминированного конечного автомата15 Определение детерминированного конечного автомата16 Объяснить разницу между недетерминированным и детерминированнымконечным автоматом17 Определение конфигурации конечного автомата18 Определение языка, допускаемого конечным автоматом19 Определение ε-замыкания для подмножества состояний НКА20 Определение расширенной функции переходов для КА21 Определение функции firstpos для поддерева в дереве регулярноговыражения22 Определение функции lastpos для поддерева в дереве регулярноговыражения23 Определение функции followpos для позиций в дереве регулярногоСтр.

1 из 13выражения24 Сформулировать соотношение между регулярными множествами иязыками, допускаемыми КА25 Определение регулярной грамматики26 Соотношение, между языками, порождаемыми КС-грамматиками, иязыками, допускаемыми недетерминированными МП автоматами27 Определение контекстно-свободной грамматики28 Определение левостороннего вывода в КС-грамматике29 Определение правостороннего вывода в КС-грамматике30 Определение сентенциальной формы31 Определение приведенной грамматики32 Определение множества FOLLOW(A)33 Определение LR(1) ситуации34 Сформулировать соотношение между языками, порождаемымиправолинейными грамматиками и языками, допускаемыми КА35 Определение однозначной КС-грамматики36 Определение неоднозначной КС-грамматики37 Определение контекстно-свободной грамматики без ε-правил38 Определение вывода в КС-грамматике39 Определение языка, порождаемого КС-грамматикой40 Определение недетерминированного МП автомата41 Определение детерминированного МП автомата42 Определение конфигурации МП автомата43 Определение языка, допускаемого МП автоматом44 Определение недетерминированного МП автомата, допускающегоопустошением магазина45 Определение множества FIRST(u)46 Определение замыкания множества LR(1) ситуаций47 Что такое леворекурсивная грамматика?Определение грамматик типа 0 по ХомскомуЕсли на грамматику G = (N, T, P, S) не накладываются никакие ограничения, то еёназывают грамматикой типа 0, или грамматикой без ограничений.Определение грамматик типа 1 (неукорачивающих) поХомскомуЕслиСтр.

2 из 131. Каждое правило грамматики, кроме S → ε, имеет вид α → β, |α| ≤ |β|2. В том случае, когда S → ε ∈ P, символ S не встречается в правых частях правилто грамматику называют грамматикой типа 1, или неукорачивающей.Определение детерминированной машины ТьюрингаДетерминированная машина Тьюринга — Tm = (Q, Г, Σ, D, q0, F)Q — конечное множество состоянийГ — конечное множество символов (конечный алфавит)Σ — входной алфавит, Σ ⊆Г\{b} (b - пустой символ)D — правила переходаD: (Q\F) × Г → Q × Г × {L, R}q0 ∈ Q — начальное состояниеF ⊆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 = a1 … ani ∈ Z — положение головки машины ТьюрингаОпределение языка, допускаемого машиной ТьюрингаСтр.

3 из 13Язык, допускаемый машиной Тьюринга — множество таких слов w, что, машинаТьюринга, находясь в состоянии (q0, w, 1) может достигнуть через конечное числопереходов состояния q ∈ F.Соотношение между языками, порождаемымиграмматиками типа 0 и языками, допускаемымимашинами ТьюрингаКласс языков, допускаемых машиной Тьюринга, эквивалентен классу языков,порождаемых грамматиками типа 0.Объяснить разницу между недетерминированной идетерминированной машиной ТьюрингаДетерминированная машина Тьюринга из данного состояния по данному символуможет сделать не более одного перехода, недетерминированная же такимсвойством не обладает.Определение линейно-ограниченного автоматаЛинейно-ограниченный автомат — это недетерминированная машина Тьюринга,которая не может выходить за область входной строки.Соотношение между языками, порождаемымиграмматиками типа 0 и языками, допускаемымилинейно-ограниченными автоматамиЛинейно-ограниченные автоматы распознают контекстно-зависимые языки (то естьязыки класса 1).

Языки класса 0 распознаются только машинами Тьюринга снеограниченной памятью.Определение регулярного множестваРегулярное множество в алфавите T определяется следующим образом:Стр. 4 из 13{} (пустое множество) — регулярное множество в алфавите 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*.Определение недетерминированного конечногоавтоматаНедетерминированный конечный автомат - M = (Q, Σ, D, q0, F)Q — конечное непустое множество состоянийΣ — входной алфавитD — правила переходаQ × ( Σ ∪ {ε} ) → 2QСтр.

5 из 13q0 ∈ 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 — текущее состояние управляющего устройства, а ω — цепочкасимволов на входной ленте, состоящая из символов под головкой и всех символовсправа от неё.Определение языка, допускаемого конечнымавтоматомАвтомат M допускает цепочку ω, если (q0, ω) * (q, ε) для некоторого q ∈ F. Языком,допускаемым автоматом M, называется множество входных цепочек,допускаемыхавтоматом M. То есть:L(M) = {ω | ω ∈ T* и (q0, ω) * (q, ε) для некоторого q ∈ F}Стр.

6 из 13Определение ε-замыкания для подмножествасостояний НКАε-замыкание множества состояний 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 узла синтаксического дерева регулярныхвыражений даёт множество позиций, которые соответствуют первым символам вцепочках, генерируемых подвыражением с вершиной n.

Построение:узел nεi≠εu|vu.vv*firstpos(n)∅{i}firstpos(u) ∪ firstpos(v)if nullable(u) then firstpos(u) ∪ firstpos(v) else firstpos(u)firstpos(v)Определение функции lastpos для поддерева в дереверегулярного выраженияФункция lastpos(n) для каждого узла n узла синтаксического дерева регулярныхвыражений даёт множество позиций, которым соответствуют последние символы вцепочках, генерируемых подвыражениями с вершиной n. Построение lastpos(n):Стр. 7 из 13узел nlastpos(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.Сформулировать соотношение между регулярнымимножествами и языками, допускаемыми КАЛюбой конечный автомат распознает регулярное множество цепочек символоввходного алфавита.