Что это за грамматика? Контекстно-зависимый или контекстно-зависимый

Question

Я изучаю Формальные Языки и Теорию автоматов, и у меня есть вопрос о проблеме в книге, на которую нет ответа. вопрос в том:

Является ли этот язык контекстным, регулярным или контекстно-зависимым?

L = {aⁿ ww^R bⁿ| w является (a + b) *, w^R является обратным к w и n>=0 }

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

Кто-нибудь может это прокомментировать?

Благодарю.

Answer 1

Язык a ⁿ ww ^R b ⁿ является языком Context Free. Мы можем написать контекстную грамматику для этого языка.

S -->  aSb | R
R -->  aRa | bRb | ^

^ является нулевым символом

КПК: для языка a ⁿ ww ^R b ⁿ

• строка префикса push an
• От себя w
• поп w в то время как сопоставить каждый символ с символом в wR
• поп все a положить в стек и сопоставить с b в суффиксе bn

Примечание: при обработке строки языка a ⁿ ww ^R b ⁿ через PDA мы не знаем, где префикс an заканчивается тогда, где w заканчивается раньше wR Начнем с того, что для этого языка мы не можем нарисовать детерминированную модель КПК, хотя недетерминированный КПК возможен. И важно то, что класс недетерминированного КПК не совпадает с классом детерминированного КПК, что означает, что языки, свободные от детерминированного контекста, не равны недетерминированному свободному контексту. (фактически детерминированный является подмножеством недетерминированного КЛЛ)