Scribd
Загрузить
5 просмотров1 страница

FormalLanguagesHomeworks 1

Документ содержит домашнее задание по теории формальных языков для студентов Московского физико-технического института. В задании представлены шесть задач, касающихся определения регулярности языков и построения регулярных выражений. Задачи охватывают различные аспекты формальных языков, включая гармонию гласных и решение уравнений с регулярными выражениями.

Загружено:

bender2716057ilovebender
Авторское право
© All Rights Reserved
Мы серьезно относимся к защите прав на контент. Если вы подозреваете, что это ваш контент, заявите об этом здесь.
Доступные форматы
Скачать в формате PDF, TXT или читать онлайн в Scribd
5 просмотров1 страница

FormalLanguagesHomeworks 1

Документ содержит домашнее задание по теории формальных языков для студентов Московского физико-технического института. В задании представлены шесть задач, касающихся определения регулярности языков и построения регулярных выражений. Задачи охватывают различные аспекты формальных языков, включая гармонию гласных и решение уравнений с регулярными выражениями.

Загружено:

bender2716057ilovebender
Авторское право
© All Rights Reserved
Мы серьезно относимся к защите прав на контент. Если вы подозреваете, что это ваш контент, заявите об этом здесь.
Доступные форматы
Скачать в формате PDF, TXT или читать онлайн в Scribd

Московский физико-технический институт.

ФПМИ МФТИ.

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


Домашнее задание №1.

Задача 1. Является ли регулярным язык слов в алфавите {a, b, c}, в которых нет двух подряд
идущих одинаковых букв?
Задача 2. Является ли регулярным язык слов в алфавите {a, b}, в которых число букв a четно,
а число букв b нечетно?
Задача 3. Является ли регулярным язык слов в алфавите {a, b, c, d}, в которых правее каждой
a обязательно встречается некоторая буква d, притом между этими буквами возможны только
буквы b?
Задача 4. Является ли регулярным язык {an | существует такое p ≥ n, что p простое и p + 2
– простое }?
Задача 5. В некоторых языковых семьях, таких как тюркская или уральская, наблюдается
явление, называемое гармонией гласных : в слове могут встречаться только гласные типа V1
или только типа V2 , но не обоих типов одновременно. Пусть в гипотетическом языке действуют
следующие правила:

1. Присутствует гармония гласных.


2. Не может идти более двух согласных подряд.
3. Слово обязательно заканчивается на согласный.

Задайте в алфавите {C, V1 , V2 }, где C означает произвольный согласный, фонетическую струк-


туру слов данного языка (постройте регулярное выражение, выражающее эту структуру).
Задача 6. Решите уравнение: X = Xf + g. f , g – регулярные выражения, ε ∈
/ L(f ).

Вам также может понравиться