У меня есть домашнее задание, и я закончил, кроме одного вопроса (см. заголовок)
Ради всего святого, я не могу понять это... поэтому я начал думать, что это вопрос с подвохом.
Сейчас я отвечу так:
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.
любая помощь / руководство были бы великолепны.