Насосная лемма используется, чтобы показать, что язык не является регулярным / не-CFL.

Question

Язык L удовлетворяет лемме накачки для обычных языков, а также лемме накачки для языков без контекста. Какое из следующих утверждений о L верно?

A. L обязательно является обычным языком.

B. L обязательно CFL, но не обычный.

C. L обязательно нерегулярен.

D. Ни один

Я выясню, где у меня возникают сомнения. Если L удовлетворяет лемме прокачки для регулярных языков, то она не обязательно регулярна. То же самое с контекстом бесплатно. Так что это может быть обычным или нерегулярным. КЛЛ или не КЛЛ. Ответ дан B, но, по моему мнению, это должен быть D. Может кто-нибудь указать, что мне не хватает.

Answer 1

Ответ Б определенно не прав.Попробуйте язык Σ *, который является абсолютно регулярным и определенно не зависит от контекста.Он также проходит условия обеих накачки лемм.Следовательно, это определенно не тот случай, когда язык является контекстно-независимым, но не регулярным.

Обе леммы прокачки дают необходимые условия для того, чтобы язык был регулярным или контекстно-свободным, а не достаточных условий для того, чтобы эти языки были регулярными или контекстно-свободными.Поэтому, если язык проходит обе леммы прокачки, он может быть регулярным и может быть не зависящим от контекста, но нет никакой гарантии, что это обязательно должно быть так.

Я почти уверен, что D - правильный выбор.

Надеюсь, это поможет!

Answer 2

Совет:

1. Лемма накачки: ¬q → ¬p где q - лемма накачки, а p - обычный язык. Именно Contrapositive означает, что если язык не удовлетворяет лемме накачки, то он не может быть обычным языком. Это всегда правда.
2. Тогда также правильно , что p → q. Подразумевается, что если язык регулярен, то он всегда удовлетворяет лемме прокачки.

Также обратите внимание, что его обратное ¬p → ¬q и обратное q → p не обязательно должны быть истинными согласно логике высказываний.