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

Материал из Викиконспекты
Версия от 04:21, 16 января 2017; 94.25.229.232 (обсуждение) (Новая страница: «Предположим детерминированный строгий автомат с единственным состоянием с элементами, ...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Предположим детерминированный строгий автомат с единственным состоянием с элементами, представленный тройкой: входной алфавит на ленте [math]\Sigma[/math], стековым алфавит [math]\Gamma[/math] и множеством переходов [math]\Delta[/math]. Мы предполагаем наличие полного порядка на [math]\Sigma[/math],и говорим, что слово [math]u[/math] короче слова [math]v[/math] если [math]|u| \lt |v|[/math] или [math]|u| = |v|[/math] и [math]u[/math] лексикографически меньше [math]v[/math]. Пусть [math]E, F, G,\dotsc[/math] - допустимые конфигурации.

Определение:
[math]E \cdot u[/math] - конфигурация [math]E[/math] после слова [math]u[/math], единственная допустимая конфигурация [math]F[/math] такая что [math](E, u) \rightarrow F[/math], которая может быть и [math]\emptyset[/math].


Определение:
Язык, задаваемой конфигурацией [math]E[/math], [math]L(E) = \{ E : (E \cdot u) = \varepsilon \}[/math].


Определение:
[math]E \sim F[/math] - две конфигурации [math]E[/math] и [math]F[/math] эквивалентны если [math]L(E) = L(F)[/math].


Равенство задаваемых языков также может быть приблизительным.

Определение:
[math]E \sim_n F, n \geq 0[/math] - конфигурафии [math]E[/math] и [math]F[/math] [math]n[/math]-эквивалентны если они принимают одни и те же слова, длина которых не больше [math]n[/math]:
для всех слов [math]w[/math], таких что [math]|w| \leq n, (E \cdot w) = \varepsilon[/math] тогда и только тогда, когда [math](F \cdot w) = \varepsilon[/math]


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


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


Определение:
[math]E = E_1G_1 + ... + E_nG_n[/math] находится в форме голова/хвост, если голова [math]E_1 + ...+E_n[/math] допустима и хотя бы один [math]E_i= \emptyset[/math], и каждый хвост [math]G_i = \emptyset[/math].


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

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

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

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


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


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

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