Является ли данный контекстно-свободный язык регулярным

Question

Решаемо ли:

1. Данная грамматика не зависит от контекста?

2. Данный рекурсивный язык не зависит от контекста?

3. Данный контекстно-свободный язык является регулярным?

Answer 1

Данный грамматик может дать нам язык и, используя язык и лемму прокачки, мы можем легко решить, является ли данный грамматик контекстно-свободным

Используя теорему Грейбаха, мы можем показать, что неразрешимо, является ли язык без контекста регулярным или нет..