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


Порождающие грамматики - часть 2


Замечание 1.4.9.

В частности, для всякого слова

имеет место

(так как возможен вывод длины 0).

Пример 1.4.10. Пусть . Тогда . Длина этого вывода - 3.

Определение 1.4.11. Язык, порождаемый грамматикой G, - это множество . Будем также говорить, что грамматика G порождает (generates) язык L(G).

Замечание 1.4.12. Существенно, что в определение порождающей грамматики включены два алфавита - и N. Это позволило нам в определении 1.4.11 "отсеять" часть слов, получаемых из начального символа. А именно, отбрасывается каждое слово, содержащее хотя бы один символ, не принадлежащий алфавиту .

Пример 1.4.13. Если , то .

Определение 1.4.14. Две грамматики эквивалентны, если они порождают один и тот же язык.

Пример 1.4.15.

Грамматика

и грамматика

эквивалентны.

Упражнение 1.4.16. Описать язык, порождаемый грамматикой

Упражнение 1.4.17. Описать язык, порождаемый грамматикой

Упражнение 1.4.18. Описать язык, порождаемый грамматикой

Упражнение 1.4.19. Описать язык, порождаемый грамматикой

Упражнение 1.4.20. Описать язык, порождаемый грамматикой

Упражнение 1.4.21. Описать язык, порождаемый грамматикой

Упражнение 1.4.22. Эквивалентны ли грамматика

и грамматика

Упражнение 1.4.23. Эквивалентны ли грамматика

и грамматика




Начало  Назад  Вперед



Книжный магазин