Теормин (2009)

Конструирование Компиляторов, Теоретический минимум (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 по Хомскому.12.

Определение недетерминированного конечного автомата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.

Объяснить разницу между недетерминированным и детерминированным конечным автоматомДетерминированный автомат является частным случаем недетерминированного автомата, который на каждом тактеработы имеет возможность перейти не более чем в одно состояние и не может делать переходы по .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 = q ∈ R {p | (q, ε) ⊢∗ (p, ε)}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) = − ( D pi, a ), 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 не встречается в правых частях правил.Регулярные грамматики — праволинейные или леволинейные регулярные грамматики.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.