19. Логика на словах.

Один из основных подходов к исследованию распознаваемых языков базируется на известной теореме Ж. Бучи о характеризации регулярных языков средствами монадической логики второго порядка. В контрольной работе необходимо изучить метод исследования распознаваемых языков, основанный на монадической логике второго порядка. Рекомендуется следующий план работы:

1) Изучить основные понятия монадической логики второго порядка (/1/, с. 328-330; /2/, с. 313-321; /3/, с. 1-2).

2) Рассмотреть приложение монадической логики второго порядка к теории языков (/2/, с. 321-324; /3/, с. 1-2).

3) Разобрать доказательство теоремы Ж.Бучи о характеризации регулярных языков средствами монадической логики второго порядка (/2/, с. 325-329; /3/, с. 1-2).

4) С помощью теоремы Ж.Бучи исследовать взаимосвязь между иерархиями языков и определяющих их формул логики первого порядка (/2/, с. 329-338; /3/, с. 8-13).

Литература, рекомендуемая для изучения темы

1 Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.

2 Pin J.-E., Perrin D. Infinite words. 2001 (в печати, текст доступен на

www.liafa.jussieu.fr/~jep/Resumes/InfiniteWords.html).

3 Pin J.-E. Logic on Words. Report LITP 94/53, Institut Blaise Pascal, 1994

(препринт).