Теормин (2009) (1134838)

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

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

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

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

Тип файла PDF

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

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

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