Теория и реализация языков программирования



Линейно-ограниченные автоматы и их связь с контекстно-зависимыми грамматиками - часть 2


Q - это множество состояний,
F \subseteq Q
- множество заключительных состояний,
\Gamma
- множество ленточных символов,
\Sigma \subseteq \Gamma
- множество входных символов,
q_0 \in Q
- начальное состояние, D- отображение из Q x ? в подмножество Q x ? x {L, R}.

? содержит два специальных символа, обычно обозначаемых © и $, - левый и правый концевые маркеры, соответственно. Эти символы располагаются сначала по концам входа и их функция - предотвратить переход головки за пределы области, в которой расположен вход.

Конфигурация M и отношение

\vdash M
, связывающее две конфигурации, если вторая может быть получена из первой применением D, определяются так же, как и для машин Тьюринга. Конфигурация M обозначается как

(q,A1A2,...,An,i) где

q \in Q, \; A_1,A_2, \ldots ,A_n \in \Gamma, i
-целое от 1 до n. Предположим, что
(p,A,L) \in D(q,A_i)
и i > 1

Будем говорить, что

(q,A_1,A_2 \ldots A_n,i)\vdash_M (p,A_1,A_2 \ldots A_{i-1}AA_{i+1} \ldots A_n,i-1)

(p,A,R) \in D(q,A_i)
и i < n, будем говорить, что

(q,A_1,A_2 \ldots A_n,i)\vdash_M (p,A_1,A_2 \ldots A_{i-1}AA_{i+1} \ldots A_n,i+1)

То есть M печатает A поверх Ai, меняет состояние на p и передвигает головку влево или вправо, но не за пределы области, в которой символы располагались исходно. Как обычно, определим отношение

\vdash *_M
как

(q, \alpha , i )\vdash *_M (q, \alpha , i )
и

Если

(q_1, \alpha_1 , i_1 )\vdash *_M (q_2, \alpha_2 , i_2 )
и
(q_2, \alpha_2 , i_2 )\vdash *_M (q_3, \alpha_3 , i_3 )
,

то

(q_1, \alpha_1 , i_1 )\vdash *_M (q_3, \alpha_3 , i_3 )

Язык, допускаемый M - это

\{w \mid w \in (\Sigma \ \{ \copyright, \$ \})^*
и
(q_0,\copyright w \$, 1) \vdash * (q, \alpha , i)
для некоторого
q \in F, \alpha \in \Gamma^*
и целого i}.

Будем называть M детерминированным, если D(q, A) содержит не более одного элемента для любых

q \in Q, A \in \Gamma
. Не известно, совпадает ли класс множеств, допускаемых детерминированными и недетеминированными ЛОА. Ясно, что любое множество, допускаемое недетерминированным ЛОА, допускается некоторой детерминированной МТ. Однако, число ячеек ленты, требуемой этой МТ, может экспоненциально зависеть от длины входа.

Класс множеств, допускаемых ЛОА, в точности совпадает с классом контекстно - зависимых языков.

Теорема 2.7. Если L - контекстно-зависимый язык, то L допускается ЛОА.

Доказательство. Пусть G = (VN, VT, P, S) - контекстно- зависимая грамматика. Построим ЛОА M такой, что он допускает язык L(G). Не вдаваясь в детали построения M, поскольку он довольно сложен, рассмотрим схему его работы. В качестве ленточных символов будем рассматривать пары

(s^1_i,s^2_i), \; \text{где} \; s^1_i \in \Sigma, \;\Sigma= V_T \cup \{@,\$ \}, \; s^2_i \; \in \Gamma, \; \Gamma = V_T \cup V_N \cup \{B \}
В начальной конфигурации лента содержит (@, B), (a1, B), ... (an, B), ($, B), где a1 ... an = w - входная цепочка, n=|w|.


Содержание  Назад  Вперед