Я видел два вопроса, и я не знаю, как на это ответить

Question

Является ли язык строк, которые не имеют форму t # t, где t произвольная строка над {0,1} CFL? Я не знаю, чтобы решить это.

Другой вопрос заключается в следующем: является ли набор, состоящий из: правил производства Граммеров, являющихся CFG, сам по себе регулярный набор? Как доказать? Я не понимаю, что означает вопрос. Спасибо.

Answer 1

Язык всех наборов правил, не зависящих от контекста, обычно будет регулярным. В зависимости от ваших точных определений и вашего представления правил, вам в основном нужно только проверить, все ли левые части имеют длину один и правильный ли формат набора.

((S,ab),(S,aSb))

может быть строкой этого языка для набора с правилами S->ab и S->aSb. Скобки никогда не вкладываются глубже 2, поэтому вам не нужен стек. Если вы действительно имеете в виду «набор, состоящий из: правил производства грамматик», у вас есть строки с единичными правилами, такими как (S,ab), что еще проще.

Что касается набора строк, которые не имеют формы t # t, то его дополнение хорошо известно как не зависящее от контекста. Поскольку КЛЛ не является закрытым по дополнению, это ничего не значит, однако. Вы можете найти ответ здесь .