Найдите недетерминированную CFL, обратная задача которой детерминирована

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

Ради всего святого, я не могу понять это... поэтому я начал думать, что это вопрос с подвохом.

Сейчас я отвечу так:

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'. Но это вводит новый недетерминизм, поскольку второй вход может быть либо a, либо b.

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

5
задан KevinCameron1337 2 December 2011 в 23:09
поделиться