Как определить, к какому классу принадлежат эти языки?

Может быть, мой ответ будет вам полезен:

L₁ = {ww | w ∈ {a, b}^* }

не является контекстно-свободным языком, потому что PDA (Push down Automata) невозможен (даже Non-Deterministic-PDA). Почему? предположим, вы помещаете первый w в стек. Чтобы сопоставить второй w с первым w, вы должны нажать первый w в обратном порядке (либо вам нужно сопоставить второй w в обратном порядке с содержимым стека), что невозможно со стеком (и мы не можем читать ввод в обратном порядке). Хотя это разрешимо, потому что можно нарисовать Turing Machine для L₁, которое всегда наполовину после конечного числа шагов.

L₃ = {ww^R | w ∈ {a, b}^* }

Язык L₃ является недетерминированным контекстно-свободным языком, потому что n-PDA возможен, но конечная автоматизация невозможна для L₃. вы также можете доказать это, используя лемму о накачке для обычных языков.

Σ* - Обычный язык (RL)

Σ* — это регулярное выражение (RE), например, если Σ = {a, b} then RE is (a + b)* RE возможно только для RL.

Примеры в моем вопросе могут быть более полезными для ты.