Найти недетерминированный КЛЛ, обратная сторона которого является детерминированной

Question

У меня есть домашнее задание, и я закончил, кроме одного вопроса (см. Заголовок)

Что касается моей жизни, я не могу понять это ... поэтому я начал думать, что это был вопрос с подвохом.

текущий ответ, который я отправлю:

L1 = {a^n b^n: n>=1} is deterministic.  And the reverse, 
L2 = {b^n a^n: n>=1} is also deterministic.  

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

Кстати, единственный другой пример, который я пытался сделать, это:

L3= {{a,b}a}

Это кажется возможным, поскольку вперед существует недетерминизм, поскольку вход может быть либо a, либо b, если за ним следует a.

и наоборот есть детерминизм, поскольку он примет только «а». Но он вводит новый недетерминизм, поскольку вторым вводом может быть либо a, либо b.

любая помощь / руководство было бы замечательно.

Answer 1

Я знаю, что крайний срок прошел, но кто-то может найти это полезным в будущем.

(a + b + c) * WcW ^ R, где W находится в (a + b) +; это недетерминировано, потому что вы не знаете, где начинается бит "WcW".

W ^ RcW (a + b + c) *, где W находится в (a + b) +; это является детерминированным, потому что вы можете написать детерминированный КПК, чтобы принимать простые палиндромы в форме "W ^ RcW" и изменять принимающее состояние, чтобы зацикливаться на любом из a, b и c.

Хитрость в том, что КПК должны читать ввод слева направо.