Настоящее издание представляет собой учебное пособие, подготовленное в соответствии с Государственным образовательным стандартом по дисциплине "Информатика". Материал изложен кратко, но четко и доступно, что позволит в короткие сроки его изучить, а также успешно подготовиться и сдать экзамен или зачет по данному предмету. Издание предназначено для студентов высших учебных заведений.
Книга известных американских ученых посвящена теории автоматов и соответствующих формальных языков и грамматик - как регулярных, так и контекстно-свободных. Во второй части рассматриваются различные машины Тьюринга, при помощи которых формализуются понятия разрешимых и неразрешимых проблем, а также определяются функции временной и емкостной оценки сложности алгоритмов. Изложение ведется строго, но доступно, и сопровождается многочисленными примерами, а также задачами для самостоятельного решения
Настоящее издание представляет собой учебное пособие, подготовленное в соответствии с Государственным образовательным стандартом по дисциплине "Информатика".