Теория формальных грамматик и автоматов

3 ВВЕДЕНИЕ Теория формальных грамматик и автоматов (ТФГиА) является в подготовке специалиста по информатике и вычислительной технике одной из важнейших дисциплин. Дисциплина эта достаточно сложная, требующая тщательной методической проработки. К сожалению, в отечественной учебной литературе имеет место заметный дефицит учебных пособий. по ТФГиА. Как известно, алгоритмические языки становятся доступными для использования лишь после создания трансляторов с этих языков, и с решением этой проблемы самым тесным образом связаны дисциплина ТФГиА и данная методическая разработка. Дело в том, что теоретические основы методов проектирования алгоритмических языков, а также конструирования трансляторов укладываются в рамки ТФГиА. Даже очень простая программа требует ввода исходных данных. Исходные данные, которые в простейшем случае могут представлять собой набор чисел, обязательно требуют выражения на некотором языке, проверки их корректности, перевода во внутренние структуры данных компьютера. Традиционно указанные особенности приято обозначать как «компиляция». Каждый уважающий себя программист обязан хорошо понимать процесс компиляции программ, что, в свою очередь приводит к необходимости знакомства с теорией формальных языков и формальных грамматик. Учебное пособие содержит сведения из теории формальных языков, составляющие основу для построения компилирующих программ (трансляторов) и включает: - сведения из языкознания (лингвистики); - математическое определение формального языка и формальной грамматики; - классификацию формальных грамматик и автоматов по Хомскому; - определение и описание процессов трансляции;