Название: Информатика (формальные языки и грамматики) - Методическая разработка(С.Е. Рояк)

Жанр: Информатика

Просмотров: 1363


Введение

 

Курс «Информатика» является разделом дискретной математики и может рассматриваться как продолжение курсов «Математическая логика» и «Теория множеств». Знать основные понятия этих дисциплин необходимо для успешного освоения данного курса, основная цель которого изучить свойства формальных моделей представления и обработки информации. Знакомство с этим курсом полезно специалистам в области прикладной математики как в общеобразовательных целях, так и ради прикладных задач (например, связанных с языками программирования). Но было бы ошибкой понимать информатику лишь как чисто программистское ремесло, как вспомогательную науку по обработке данных или как учение о вычислительных машинах. На самом деле через эти задачи информатика вырастает в фундаментальную науку, которая, как уже говорилось, занимается вопросами представления и обработки информации. Материал данного курса в дальнейшем может быть применен в курсах, связанных с проектированием систем переработки информации: трансляторов, операционных систем, баз данных, а также с моделированием и описанием сложных связей или процессов методами информатики.

Настоящее пособие представляет собой практикум по теории формальных грамматик. В нем строятся и изучаются формальные грамматики – абстрактные объекты, которые служат моделями конкретных систем грамматических правил. Формальные грамматики определяют формальные языки, которые, в свою очередь, служат моделями совокупности «правильных текстов».

Возникнув в результате усилий, направленных на выработку точных методов описания естественных языков, теория грамматик сомкнулась, с одной стороны, с теоретической лингвистикой, с другой – с теорией алгоритмов и автоматов. Понятия и методы, используемые этими теориями, получили в формальных грамматиках своеобразную интерпретацию и были развиты в новых направлениях. Место теории грамматик внутри общей теории алгоритмов может быть охарактеризовано следующим образом: теория грамматик изучает в определенном аспекте «внутреннее строение» рекурсивных множеств некоторых специальных классов.

Практические приложения теории грамматик, прежде всего, связаны с лингвистикой, для которой формальные грамматики – это удобный метаязык. Кроме того, формальные грамматики нашли широкое применение при описании языков программирования и разработки эффективных алгоритмов трансляции для последних. Необходимо отметить, что в курсе «Информатики» изучаются лишь основы теории грамматик, ее классические понятия и факты, поэтому задачи и упражнения данного практикума направлены на изучение этих понятий.