Теормин по конструлям 2010 (1131631), страница 2

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

Текст из файла (страница 2)

3)Бесполезными называются бесплодные и недостижимые символы.

4)Грамматика без бесполезных символов — приведенная грамматика.

5)Определение множества FOLLOW(A).

Пусть A — нетерминал. Тогда FOLLOW(A) — множество терминалов a, которые могут появиться непосредственно справа от A в некоторой , то есть, множество терминалов a таких, что существует вывод вида S ⇒* uAav для некоторых u и v.

6)Определение LR(1) ситуации.

LR(1)-ситуацией называется пара [A → α . β, a], где A → α β — правило грамматики, a — терминал или правый концевой маркер $. Вторая компонента ситуации называется аванцепочкой.

7)Определение множества FIRST(u).

Если u — любая строка символов грамматики, положим FIRST(u) — множество терминалов, с которых начинаются строки, выводимые из u. Если u ⇒* ε, то ε так же принадлежит FIRST(u).

8)Определение замыкания множества LR(1) ситуаций.

Пусть есть множество ситуаций I тогда определим функцию closure(I) как добавление к I ситуаций вида [B → .γ, b] для каждых ситуации [A → α.Bβ, a], правила вывода B → γ, принадлежащего Г, каждого терминала b из FIRST(βa), пока это возможно.

Автоматы с магазинной памятью, линейно-ограниченные автоматы, МТ.

1)Определение недетерминированного МП автомата.

Недетерминированный автомат с магазинной памятью (МП-автомат) — семёрка M = (Q, T, Г, D, q₀, Z₀, F), где

1. Q — конечное множество состояний, представляющее всевозможные состояния управляющего устройства

2. T — конечный входной алфавит

3. Г — конечный алфавит магазинных символов

4. D — отображение множества Q × (T ∪ {ε}) × Г в множество всех конечных подмножеств Q × Г*, называемое функцией переходов

5. q₀ ∈Q — начальное состояние управляющего устройства

6. Z₀ ∈Г — символ, находящийся в магазине в начальный момент (начальный символ магазина)

7. F ⊆Q — множество заключительных состояний

2)Определение детерминированного МП автомата.

Детерминированный автомат с магазинной памятью (МП-автомат) — семёрка M = (Q, T, Г, D, q₀, Z₀, F), где

1. Q — конечное множество состояний, представляющее всевозможные состояния управляющего устройства

2. T — конечный входной алфавит

3. Г — конечный алфавит магазинных символов

4. D — отображение множества Q × (T ∪ {ε}) × Г в множество всех конечных подмножеств Q × Г*, называемое функцией переходов

5. q₀ ∈ Q — начальное состояние управляющего устройства

6. Z₀ ∈ Г — символ, находящийся в магазине в начальный момент (начальный символ магазина)

7. F ⊆ Q — множество заключительных состояний

Кроме того, должны выполняться следующие условия:

1. Множество D(q, a, Z) содержит не более одного элемента для любых q ∈ Q, a ∈ T ∪ {ε}, Z₀ ∈ Г

2. Если D(q, ε, Z) ≠ ∅, то D(q, a, Z) = ∅ для всех a ∈ T

3)Определение конфигурации МП автомата.

Конфигурацией автомата с магазинной памятью (МП автомата) называется тройка (q, w, u), где

• q ∈ Q — текущее состояние магазинного устройства

• w ∈ T* — непрочитанная часть входной цепочки; первый символ цепочки w находится под входной головкой; если w = ε, то считается, что входная лента прочитана

• u ∈ Г* — содержимое магазина; самый левый символ цепочки u считается вершиной магазина; если u = ε, то магазин считается пустым

4)Определение языка, допускаемого МП автоматом.

Цепочка w допускается МП автоматом, если (q₀, w, Z₀)⊢* (q, ε, u) для некоторых q ∈ F и u ∈ Г*. Язык, допускаемый МП-автоматом M — множество всех цепочек, допускаемых автоматом M.

5)Определение недетерминированного МП автомата, допускающего опустошением магазина.

Цепочка w допускается МП автоматом, если (q₀, w, Z₀)⊢* (q, ε, ε) для некоторого q ∈ Q. В таком случае говорят, что автомат допускает цепочку опустошением магазина.

6)Соотношение, между языками, порождаемыми КС-грамматиками, и языками, допускаемыми недетерминированными МП автоматами.

Они совпадают.

7)Определение детерминированной машины Тьюринга.

Детерминированная машина Тьюринга — T_m = (Q, Г, Σ, D, q₀, F)

• Q — конечное множество состояний

• Г — конечное множество символов (конечный алфавит)

• Σ — входной алфавит, Σ ⊆ Г\{b} (b - пустой символ)

• D — правила перехода

  • D: (Q\F) × Г → Q × Г × {L, R}

• q₀ ∈ Q — начальное состояние

• F ⊆ Q — множество конечных состояний

8)Определение недетерминированной машины Тьюринга.

Недетерминированная машина Тьюринга — T_m = (Q, Г, Σ, D, q₀, F)

• Q — конечное множество состояний

• Г — конечное множество символов (конечный алфавит)

• Σ — входной алфавит, Σ ⊆ Г\{b} (b - пустой символ)

• D — правила перехода

  • D: (Q\F) × Г → 2^{Q × Г × {L, R}}

• q₀ ∈ Q — начальное состояние

• F ⊆ Q — множество конечных состояний

9)Определение конфигурации машины Тьюринга.

Конфигурацией машины Тьюринга называется тройка (q, w, i), где

• q ∈ Q — состояние машины Тьюринга

• w ∈ Г* — вход, помещаемый на ленту машины Тьюринга, w = a₁ … a_n

• i ∈ Z — положение головки машины Тьюринга

10)Определение языка, допускаемого машиной Тьюринга.

Язык, допускаемый машиной Тьюринга — множество таких слов w, что, машина Тьюринга, находясь в состоянии (q₀, w, 1) может достигнуть через конечное число переходов состояния q ∈ F.

11)Соотношение между языками, порождаемыми грамматиками типа 0 и языками, допускаемыми машинами Тьюринга.

Класс языков, допускаемых машиной Тьюринга, эквивалентен классу языков, порождаемых грамматиками типа 0.

12)Объяснить разницу между недетерминированной и детерминированной машиной Тьюринга.

Детерминированная машина Тьюринга из данного состояния по данному символу может сделать не более одного перехода, недетерминированная же таким свойством не обладает. 13)Определение линейно-ограниченного автомата.

Линейно-ограниченный автомат — это недетерминированная машина Тьюринга, которая не может выходить за область входной строки.

14)Соотношение между языками, порождаемыми грамматиками типа 0 и языками, допускаемыми линейно-ограниченными автоматами.

Линейно-ограниченные автоматы распознают контекстно-зависимые языки (то есть языки класса 1). Языки класса 0 распознаются только машинами Тьюринга с неограниченной памятью.

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

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