Математическая теория формальных языков
в теоретической информатике. Неудивительно, что
Цель этого курса - познакомить читателя с некоторыми основополагающими моделями и результатами, используемыми в теоретической информатике. Неудивительно, что они относятся к математике, а не к какой-либо другой области знаний - ведь в науке о компьютерах именно математические абстракции являются самыми плодотворными.
Рассматриваемые здесь идеи и результаты принадлежат теории формальных языков, грамматик и автоматов. По существу, эта теория описывает некоторые ограниченные абстрактные машины, способные выполнять определенные операции со строками. Например, конечный автомат может выяснить, содержит ли некоторый файл определенное слово, а автомат с магазинной памятью способен определить, правильна ли система вложенных круглых, квадратных и фигурных скобок.
Как подсказывает само название курса, основным объектом рассмотрения является формальный язык - произвольное множество конечных последовательностей символов, взятых из некоторого конечного множества (такие последовательности называются словами). Важность формальных языков для теоретической информатики обусловлена тем, что наиболее простой и удобной моделью данных, используемых в компьютерных программах, является конечная последовательность, каждый элемент которой взят из некоторого заранее зафиксированного конечного множества (так как для хранения этого элемента отводится фиксированный объем памяти).
В первой лекции дается классификация формальных языков в соответствии с иерархией Хомского: автоматные языки, контекстно-свободные (или бесконтекстные) языки, контекстные (или контекстно-зависимые) языки, языки типа 0. Если исключить языки, содержащие пустое слово, то названные классы вложены друг в друга (здесь они перечислены в возрастающем порядке).
В лекциях 2-6
рассматривается самый узкий из этих классов - класс автоматных (или праволинейных, или регулярных) языков, обладающий многими свойствами, важными для приложений. Например, разрешима проблема равенства автоматных языков (естественно, надо сначала договориться о способе конечного задания языка), пересечение двух автоматных языков тоже является автоматным и т.д.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий