Теормин (2010) (Олеся) (1134771), страница 2

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

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

T — конечный входной алфавит3. Г — конечный алфавит магазинных символов4. D — отображение множества Q × (T ∪{ε}) × Г в множество всех конечныхподмножеств Q × Г*, называемое функцией переходов5. q0 ∈Q — начальное состояние управляющего устройства6. Z0 ∈Г — символ, находящийся в магазине в начальный момент (начальный символмагазина)7.

F ⊆Q — множество заключительных состоянийКроме того, должны выполняться следующие условия:1. Множество D(q, a, Z) содержит не более одного элемента для любых q ∈Q, a ∈T ∪{ε}, Z0 ∈Г2. Если D(q, ε, Z) ≠ ∅, то D(q, a, Z) = ∅ для всех a ∈T3)Определение конфигурации МП автомата.Конфигурацией автомата с магазинной памятью (МП автомата) называется тройка (q, w, u),где· q ∈Q — текущее состояние магазинного устройства· w ∈T* — непрочитанная часть входной цепочки; первый символ цепочки w находитсяпод входной головкой; если w = ε, то считается, что входная лента прочитана· u ∈Г* — содержимое магазина; самый левый символ цепочки u считается вершиноймагазина; если u = ε, то магазин считается пустым4)Определение языка, допускаемого МП автоматом.Цепочка w допускается МП автоматом, если (q0, w, Z0) * (q, ε, u) для некоторых q ∈F иu ∈Г*. Язык, допускаемый МП-автоматом M — множество всех цепочек, допускаемыхавтоматом M.5)Определение недетерминированного МП автомата, допускающего опустошениеммагазина.Цепочка w допускается МП автоматом, если (q0, w, Z0) * (q, ε, ε) для некоторого q ∈Q.

Втаком случае говорят, что автомат допускает цепочку опустошением магазина.6)Соотношение, между языками, порождаемыми КС-грамматиками, и языками,допускаемыми недетерминированными МП автоматами.Они совпадают.7)Определение детерминированной машины Тьюринга.Детерминированная машина Тьюринга — Tm = (Q, Г, Σ, D, q0, F)····Q — конечное множество состоянийГ — конечное множество символов (конечный алфавит)Σ — входной алфавит, Σ ⊆Г\{b} (b - пустой символ)D — правила перехода· D: (Q\F) × Г → Q × Г × {L, R}· q0 ∈Q — начальное состояние· F ⊆Q — множество конечных состояний8)Определение недетерминированной машины Тьюринга.Недетерминированная машина Тьюринга — Tm = (Q, Г, Σ, D, q0, F)· Q — конечное множество состояний· Г — конечное множество символов (конечный алфавит)· Σ — входной алфавит, Σ ⊆Г\{b} (b - пустой символ)· D — правила перехода· D: (Q\F) × Г → 2Q × Г × {L, R}· q0 ∈Q — начальное состояние· F ⊆Q — множество конечных состояний9)Определение конфигурации машины Тьюринга.Конфигурацией машины Тьюринга называется тройка (q, w, i), где· q ∈Q — состояние машины Тьюринга· w ∈Г* — вход, помещаемый на ленту машины Тьюринга, w = a1 … an· i ∈Z — положение головки машины Тьюринга10)Определение языка, допускаемого машиной Тьюринга.Язык, допускаемый машиной Тьюринга — множество таких слов w, что, машина Тьюринга,находясь в состоянии (q0, w, 1) может достигнуть через конечное число переходов состоянияq ∈F.11)Соотношение между языками, порождаемыми грамматиками типа 0 и языками,допускаемыми машинами Тьюринга.Класс языков, допускаемых машиной Тьюринга, эквивалентен классу языков, порождаемыхграмматиками типа 0.12)Объяснить разницу между недетерминированной и детерминированной машинойТьюринга.Детерминированная машина Тьюринга из данного состояния по данному символу можетсделать не более одного перехода, недетерминированная же таким свойством не обладает.13)Определение линейно-ограниченного автомата.Линейно-ограниченный автомат — это недетерминированная машина Тьюринга, которая неможет выходить за область входной строки.14)Соотношение между языками, порождаемыми грамматиками типа 0 и языками,допускаемыми линейно-ограниченными автоматами.Линейно-ограниченные автоматы распознают контекстно-зависимые языки (то есть языкикласса 1).

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

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

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