Эквивалентность ДМП-автоматов

2017-01-16T01:21:35Z

94.25.229.232: Новая страница: «Предположим детерминированный строгий автомат с единственным состоянием с элементами, ...»

Предположим детерминированный строгий автомат с единственным состоянием с элементами, представленный тройкой: входной алфавит на ленте <tex>\Sigma</tex>, стековым алфавит <tex>\Gamma</tex> и множеством переходов <tex>\Delta</tex>. Мы предполагаем наличие полного порядка на <tex>\Sigma</tex>,и говорим, что слово <tex>u</tex> короче слова <tex>v</tex> если <tex>|u| < |v|</tex> или <tex>|u| = |v|</tex> и <tex>u</tex> лексикографически меньше <tex>v</tex>. Пусть <tex>E, F, G,\dotsc</tex> - допустимые конфигурации.
{{Определение
|definition=<tex>E \cdot u</tex> - '''конфигурация <tex>E</tex> после слова <tex>u</tex>''', единственная допустимая конфигурация <tex>F</tex> такая что <tex>(E, u) \rightarrow F</tex>, которая может быть и <tex>\emptyset</tex>.
}}
{{Определение
|definition=Язык, задаваемой конфигурацией <tex>E</tex>, <tex>L(E) = \{ E : (E \cdot u) = \varepsilon \}</tex>.
}}
{{Определение
|definition=<tex>E \sim F</tex> - две конфигурации <tex>E</tex> и <tex>F</tex> '''эквивалентны''' если <tex>L(E) = L(F)</tex>.
}}

Равенство задаваемых языков также может быть приблизительным.
{{Определение
|definition=<tex>E \sim_n F, n \geq 0</tex> - конфигурафии <tex>E</tex> и <tex>F</tex> '''<tex>n</tex>-эквивалентны''' если они принимают одни и те же слова, длина которых не больше <tex>n</tex>:
<br>для всех слов <tex>w</tex>, таких что <tex>|w| \leq n, (E \cdot w) = \varepsilon</tex> тогда и только тогда, когда <tex>(F \cdot w) = \varepsilon</tex>
}}

{{Утверждение
|statement=
Справедливы следующие факты:
# <tex>E \sim F</tex> тогда и только тогда, когда для любого <tex> n \geq 0</tex> выполняется <tex>E \sim_n F</tex>
# Если <tex>E \nsim F</tex>, то существует <tex> n \geq 0</tex> такой, что <tex>E \sim_n F</tex> и <tex>E \nsim_{n+1} F</tex>
# Если <tex>E \sim F</tex>, то для любого <tex>u \in \Sigma^*</tex>, <tex>(E \cdot u) \sim (F \cdot u)</tex>.
# <tex>E \sim_{n} F</tex>, тогда и только тогда, когда для любого <tex>u \in \Sigma^*</tex>, где <tex>|u| \leq n</tex>, <tex>(E \cdot u) \sim_{n-|u|} (F \cdot u)</tex>.
# Если <tex>E \sim_{n} F</tex> и <tex>0 \leq m < n</tex>, то <tex>E \sim_{m} F</tex>.
# Если <tex>E \sim_{n} F</tex> и <tex>F \nsim_{n} G</tex>, то <tex>E \nsim_{n} G</tex>.
}}

{{Определение
|definition=Для каждого стекового символа <tex>X</tex> словом <tex>w(X)</tex> называется самое короткое слово в множестве <tex>\{u : (X \cdot u) = \varepsilon \}</tex>
}}

{{Определение
|definition=<tex>E = E_1G_1 + ... + E_nG_n</tex> находится в форме голова/хвост, если голова <tex>E_1 + ...+E_n</tex> допустима и хотя бы один <tex>E_i= \emptyset</tex>, и каждый хвост <tex>G_i = \emptyset</tex>.
}}

Приведём некоторые свойства формы голова/хвост. Эквивалентность и n-эквивалентность языков согласуются с операциями <tex>+</tex> и суммы. Следовательно, форма голова/хвост позволяет подставить эквивалентное выражение в хвост (т.к. допустимость сохраняется).

{{Утверждение
|statement=
Пусть <tex>E = E_1G_1 + ... + E_nG_n</tex>, тогда справедливы следующие факты:
# Если <tex>(E_i \cdot u) = \varepsilon</tex>, то для всех <tex>j \neq i</tex> выполняется <tex>(E_j \cdot u) = \emptyset</tex> и <tex>(E \cdot u) = G_i</tex>
# Если <tex>(E_i \cdot u) = \emptyset</tex>, то <tex>(E \cdot u) = (E_1 \cdot u)G_1 + ... + (E_n \cdot u)G_n</tex>.
# Если <tex>H_i \neq \emptyset, 1 \leq i \leq n</tex>, то <tex>E_1H_1 + ... + E_nH_n</tex> в форме голова/хвост.
# Если каждая <tex>H_i \neq \emptyset</tex> и каждая <tex>E_i \neq \varepsilon</tex> и для каждого <tex>j</tex> такого, что <tex>E_j \neq \emptyset</tex> выполняется <tex>H_j \sim_m G_j</tex>, то <tex>E \sim{m+1} E_1H_1 + ... + E_nH_n</tex>.
# Если <tex>H_i \sim G_i, 1 \leq i \leq n</tex>, то <tex>E \sim E_1H_1 + ... + E_nH_n</tex>.
}}

Две конфигурации могут иметь одинаковые головы и разные хвосты, или одинаковые хвосты и различие в головах. Если <tex>E</tex> представлена в форме голова/хвост<tex>E_1G_1 + ... + E_nG_n</tex> и <tex>F</tex> имеет схожую форму голова/хвост <tex>F_1G_1 + ... + E_nF_n</tex>, имеющая тот же самый хвост. Несоответствие между <tex>E</tex> и <tex>F</tex>, соответственное этому представлению - это <tex>max\{|E_i|, |F_i| : 1 \leq i \leq n\}</tex>. Если несоответствие равно 0, то конфигурации одинаковы.

'''Замечание:''' любая пара конфигураций <tex>E</tex> и <tex>F</tex> имеет форму голова/хвост включающую в себя одинаковые хвосты: <tex> E = EG</tex> и <tex>F = FG</tex>, где <tex>G = \varepsilon</tex>.

{{Определение
|definition= Если <tex>E = E_1G_1 + ... + E_nG_n</tex> и <tex>F = F_1F_1 + ... + F_nF_n</tex>, тогда <tex>F</tex> в его форме голова/хвост - '''хвостовое дополнение <tex>E</tex>''' в его форме голова/хвост обеспечивается <tex>H_i = K^i_1G_1 + ... + K^i_nG_n, 1 \leq i \leq m</tex>. Когда <tex>F</tex> - хвостовое дополнение <tex>E</tex>, относящиеся к нему дополнение <tex>e</tex> - кортеж из m элементов <tex>(K^1_1+...+K_n^1,...,K_1^m +...+K_n^m)</tex> без <tex>G_is</tex>, и говорится, что <tex>F</tex> дополняет <tex>E</tex> с помощью <tex>e</tex>.
}}

Можно рассматривать дополнения как матрицы. Если <tex>E''</tex> расширяет <tex>E'</tex> с помощью <tex>e</tex> и <tex>E'</tex> расширяет <tex>E</tex> с помощью <tex>f</tex>, то <tex>E''</tex> расширяет <tex>E</tex> с помощью <tex>ef</tex>(в смысле умножения матриц).

Особый случай расширения возникает когда хвосты одинаковы. Если <tex>E = E_1G_1 + ... + E_nG_n</tex> и <tex>F = F_1G_1+...+F_nG_n</tex>, тогда <tex>F</tex> расширяет <tex>E</tex> с помощью <tex>e = ( \varepsilon + \emptyset +... + \emptyset ,..., \emptyset + \emptyset +...+ \varepsilon)</tex>. Расширение <tex>e</tex> сокращается до тождества <tex>\varepsilon</tex> (аналог единичной матрицы).

Викиконспекты - Вклад участника [ru]

Эквивалентность ДМП-автоматов