Я хочу решить задачу 2.24 «Введение в теорию вычислений» Sipser 3-е издание, ниже:
Пусть G будет следующей грамматикой:
S → T-
T → TaTb | TbTa | ε
(- это конечный символ для обозначенных конечным языком языков)
Используйте DK-тест, чтобы показать, что G является DCFG.
Опишите DPDA, который распознает L (G)
Я пытался использовать DK-тест, но это показало мне, что G не DCFG, но это невозможно, потому что я создаю DPDA, который распознает L (G).
Может кто-нибудь сказать мне, почему я неправильно провожу DK-тест?
Я не могу публиковать фотографии своей работы (потому что у меня недостаточно репутации), но я могу объяснить, что я сделал: я создаю DFA DK для шоу, что G - DCFG, но следуя символам TaTb, я достигаю в состоянии DFA DK с 2 полными правилами
T → ТАТБ.
T →. * * Тысяча двадцать-одна
и это означает, что грамматика G не является DCFG, но это не так. Я не вижу, что я делаю неправильно.