Предположим детерминированный строгий автомат с единственным состоянием с элементами, представленный тройкой: входной алфавит на ленте [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] |
| Утверждение: |
Справедливы следующие факты:
- [math]E \sim F[/math] тогда и только тогда, когда для любого [math] n \geq 0[/math] выполняется [math]E \sim_n F[/math]
- Если [math]E \nsim F[/math], то существует [math] n \geq 0[/math] такой, что [math]E \sim_n F[/math] и [math]E \nsim_{n+1} F[/math]
- Если [math]E \sim F[/math], то для любого [math]u \in \Sigma^*[/math], [math](E \cdot u) \sim (F \cdot u)[/math].
- [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].
- Если [math]E \sim_{n} F[/math] и [math]0 \leq m \lt n[/math], то [math]E \sim_{m} F[/math].
- Если [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], тогда справедливы следующие факты:
- Если [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]
- Если [math](E_i \cdot u) = \emptyset[/math], то [math](E \cdot u) = (E_1 \cdot u)G_1 + ... + (E_n \cdot u)G_n[/math].
- Если [math]H_i \neq \emptyset, 1 \leq i \leq n[/math], то [math]E_1H_1 + ... + E_nH_n[/math] в форме голова/хвост.
- Если каждая [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].
- Если [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] (аналог единичной матрицы).
