Слова с одинаковым правым и левым ассоциативным произведением

Я начал изучать недетерминированные автоматы, используя книгу Хопкрофта и Уллмана . Я застрял в проблеме, которая показалась мне очень интересной:

Дать недетерминированный конечный автомат, принимающий все строки, имеющие одинаковое значение, при оценке слева направо как справа налево путем умножения в соответствии со следующей таблицей:

$\qquad \displaystyle\begin{array}{c|ccc} \times & a & b & c \\ \hline a & a & a & c \\ b & c & a & b \\ c & b & c &a \end{array}$

Поэтому, если у нас есть строка , произведение слева направо равно ( a × b ) × c = a × c = c, а произведение справа налево равно a × ( b × c ) = a × b $abc$
$(a \times b) \times c=a \times c=c$
$a \times (b \times c)=a \times b=a$

Таким образом, не должен быть приемлемым для автоматов. Для меня очевидно, что любая строка a a ∗ или b b ∗ или c c ∗ является допустимой строкой (их правая и левая оценка работают над одними и теми же частичными строками). Легко дать NFA, который описывает оценку слева направо, но проблема в том, что если машина пытается вычислить оценку справа налево, я думаю, что ей нужно знать длину строки (поэтому необходима бесконечная память).$abc$$aa^*$$bb^*$$cc^*$

Итак, как недетерминированные автоматы могут оценить справа налево, чтобы сравнить с оценкой слева направо?

Первый трюк заключается в том, чтобы рассматривать таблицу умножения как таблицу переходов автомата где каждое состояние представляет букву в таблице умножения, но пока не беспокоится о принятии. Так что буквы слева и в теле таблицы на самом деле являются состояниями - было бы точнее записать их как q a , q b , q c , но я не буду. Буквы в верхней части являются входными данными.$A$$q_a, q_b, q_c$

Затем создайте автомат (« T » для транспонирования) для обратного умножения путем транспонирования A :$A_T$$T$$A$

$\qquad \displaystyle\begin{array}{c|ccc} A_T & a & b & c \\ \hline a & a & c & b \\ b & a & a & c \\ c & c & b & a \end{array}$

Таким образом, переводит вас в состояние c , и , как вы заметили, A T ( c b a ) переходит в состояние a of A $A(abc)$$c$$A_T(cba)$$a$$A_T$

Тем не менее, предполагает, что вы идете справа налево, а мы все еще хотим идти слева направо. Таким образом, второй трюк состоит в том, чтобы перевернуть автомат (а не умножение, которое бы просто вернуло нас, если бы мы начали), путем обращения всех стрелок в обратном направлении , что приводит к недетерминированному автомату A T R, указанному в таблице переходов ниже, с подмножества, обозначенные каскадными буквами, чтобы курица не царапалась, поэтому a c действительно { a , c } . (надеюсь, я все понял - кажется, работает).$A_T$$A_{TR}$$ac$$\{a,c\}$

$\qquad \displaystyle\begin{array}{c|ccc} A_{TR} & a & b & c \\ \hline a & ab & b & c \\ b & ∅ & c & a \\ c & c & a & b \\ \hline ab & ab & bc & ac \\ bc & c & ac & abc \\ ac & abc & ab & bc \\ abc & abc & abc & abc \\ ∅ & ∅ & ∅ & ∅ \end{array}$

Вы можете интерпретировать это как недетерминированный автомат только с тремя строками над линией или с определенной версией со всеми 8 строками.

Наконец, машиной для решения проблемы является автомат перекрестных произведений исходных и A T R , то есть A × A T R для выполнения пересечения двух автоматов (нам больше не нужен A T ) , × Т Р имеет состояния , которые представляют собой пары , такие как ⟨ с , в с ⟩ . Функция перехода запускает A и A T R независимо. Один начальное состояние ⟨ 1 , 1 $A$$A_{TR}$$A \times A_{TR}$$A_T$$A \times A_{TR}$$\langle a,ac\rangle$$A$$A_{TR}$$\langle 1,1 \rangle$переходит в при входе а , в ⟨ б , б ⟩ при входе б и т.д. $\langle a,a \rangle$$a$$\langle b,b \rangle$$b$

Принимая состояния в неопределенных версиях являются и т.д. В детерминированной версии, принимая состояния пары , в которых первый компонент ∈ второго компонента набора, например, ⟨ в , ⟩ или ⟨ б , б с ⟩ .$\langle a,a \rangle$$\in$$\langle a,a \rangle$$\langle b,bc \rangle$

дополненное и определенное, как показано, имеет 25 = 3 ⋅ 8 + 1 состояний, так что извините, если я не напишу это подробно. Но недетерминированная версия имеет только 10 = 3 ⋅ 3 + 1 состояний.$A \times A_{TR}$$25=3\cdot 8+1$$10=3\cdot 3+1$

Если L регулярный язык, то L R , язык, состоящий изреверсавсех слов в L , также является регулярным. Примите это как упражнение.$(\ast)$$L$$L^R$$L$

Как это помогает нам решить проблему? Пусть - языки, состоящие из всех строк, которые оцениваются как a , b , c при оценке слева направо. Интересующий вас язык ( L a ∩ L R a ) ∪ ( L b ∩ L R b ) ∪ ( L c ∩ L R c ) . Это показывает, что если вы знаете, как доказать $L_a,L_b,L_c$$a,b,c$

На самом деле, если вы используете идею доказательства , то, вероятно, вы можете просто пойти дальше и построить автомат. Итак, давайте рассмотрим это. В частности, давайте попробуем построить NFA для L R a , языка всех строк, которые оцениваются как a при оценке справа налево.$(\ast)$$L_a^R$$a$

$b$$b$$bx = a$$x = b$$c$$a$$a$$b$

Этот намек должен дать вам достаточно, чтобы подумать и, надеюсь, решить проблему.

Милый.

$\overrightarrow x \xrightarrow{\;y\;} \overrightarrow z$$x \cdot y = z$$\{\overrightarrow a,\overrightarrow b,\overrightarrow c\}$$\overrightarrow 1$$\overrightarrow 1 \xrightarrow{\;x\;} \overrightarrow x$$x$$\overrightarrow x$$x$

Теперь давайте создадим автомат, который вычисляет произведение справа налево. Этот будет недетерминированным. Как мы это делаем? Просто ... Чтобы пойти в другом направлении, просто поменяйте местами все : стрелки и направление продукта.

$\overrightarrow{x} \xrightarrow{\;y\;} \overrightarrow{x \cdot y\:}$$\overleftarrow{x \cdot y\:} \xleftarrow{\;x\;} \overleftarrow{y}$$\overleftarrow{x} \xleftarrow{\;y\;} \overleftarrow{y \cdot x\:}$,

$\overleftarrow 1$

$(\overrightarrow{x_1}, \overleftarrow{x_2}) \xrightarrow{\;y\;} (\overrightarrow{z_1}, \overleftarrow{z_2})$$\overrightarrow{x_1} \xrightarrow{\;y\;} \overrightarrow{z_1}$$\overleftarrow{x_2} \xrightarrow{\;y\;} \overleftarrow{z_2}$$(\overrightarrow 1, \overleftarrow x)$$(\overrightarrow x, \overleftarrow x)$$x$

Кажется, что ваша главная проблема заключается в использовании недетерминизма, поэтому позвольте мне остановиться на этом подробнее.

Основная идея, которую используют другие, заключается в том, что недетерминированная машина может угадать конечный результат.

$abc$

• $a$$a$$bc$$a$$b$
  • $a$$b$$b$
    • $b$$c$
  • $b$$b$$c$
    • $c$$c$
• $b$$a$
• $c$$a$$bc$$c$
  • $c$$b$$a$
    • $a$$c$

Как видите, NFA может угадывать и проверять все возможные вычисления снизу вверх . Поскольку принятый язык определяется как набор строк, который принимается хотя бы одним прогоном , все неприемлемые прогоны на входе игнорируются; НФА "всегда угадывает правильно".

Теперь NFA легко запомнить свой первый выбор до конца. Если он принимает, он может сравнить запомненный символ с lr-произведением (детерминистически), полученным параллельно (то, как пересечение языка относится к NFA, наверняка описано в Ullman / Hopcroft и любом другом базовом учебнике).