Математическая теория формальных языков



             

Лемма о разрастании для контекстно-свободных языков - часть 2


является объединением некоторого семейства арифметических прогрессий, причем у каждой прогрессии первый член и шаг не больше числа p. Так как существует лишь конечное число прогрессий натуральных чисел с таким ограничением, рассматриваемое семейство конечно. Следовательно, язык L является автоматным (используем пример 2.1.18).

Упражнение 9.1.4. Является ли контекстно-свободным язык ?

Упражнение 9.1.5. Является ли контекстно-свободным язык ?

Упражнение 9.1.6. Является ли контекстно-свободным язык ?

Упражнение 9.1.7. Является ли контекстно-свободным язык {am | m простое}?

Упражнение 9.1.8. Является ли контекстно-свободным язык ?

Упражнение 9.1.9. Является ли контекстно-свободным язык ?

Упражнение 9.1.10. Является ли контекстно-свободным язык ?

Упражнение 9.1.11. Является ли контекстно-свободным язык ?

Упражнение 9.1.12. Является ли контекстно-свободным язык ?

Упражнение 9.1.13. Является ли контекстно-свободным язык {akbmcn | k < max(m,n)}?

Упражнение 9.1.14. Является ли контекстно-свободным язык {akbmcn | k > max(m,n)}?

Упражнение 9.1.15. Является ли контекстно-свободным язык

Упражнение 9.1.16. Какому классу принадлежит язык, порождаемый грамматикой

Упражнение 9.1.17. Существуют ли такие контекстно-свободные языки

и , что язык

не является контекстно-свободным?




Содержание  Назад  Вперед