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

Formal Languages Homeworks

Документ содержит домашнее задание по теории формальных языков, состоящее из семи задач, связанных с построением недетерминированных конечных автоматов (НКА) и анализом их свойств. Задачи включают распознавание определенных языков, доказательства о классах языков и исследование подпоследовательностей автоматных языков. Каждая задача требует применения теоретических знаний о формальных языках и автоматах.

Загружено:

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

Formal Languages Homeworks

Документ содержит домашнее задание по теории формальных языков, состоящее из семи задач, связанных с построением недетерминированных конечных автоматов (НКА) и анализом их свойств. Задачи включают распознавание определенных языков, доказательства о классах языков и исследование подпоследовательностей автоматных языков. Каждая задача требует применения теоретических знаний о формальных языках и автоматах.

Загружено:

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

ФПМИ МФТИ.

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


Домашнее задание №2

Задача 1. Постройте недетерминированный конечный автомат, распознающий множество


слов {(ab)k (aab)l | k, l > 0} (Σ = {a, b}).

Задача 2. Постройте недетерминированный конечный автомат для языка слов, задаваемых


выражением a(a(ab)∗ a(ab)∗ + b)∗ .

Задача 3. Постройте НКА для языков слов, не содержащих подслово bxa, где x ∈ {a, b, c}.

Задача 4. Докажите, что класс языков, распознаваемых НКА с одним начальным и одним
завершающим состоянием, в которых разрешены только однобуквенные переходы, НЕ совпа-
дает с классом всех автоматных языков.

Задача 5. Верно ли утверждение предыдущей задачи для класса языков без пустого слова
(в формулировке предыдущей задачи необходимо заменить "класс языков"на "класс языков,
не содержащих пустое слово")?

Задача 6. Достаточно ли в определении НКА с однобуквенными переходами двух завер-


шающих состояний?

Задача 7. Пусть L — автоматный язык. Будет ли автоматным язык Subseqk (L), состоящий
из таких подпоследовательностей слов из L, в которых длины “разрывов в середине” не превы-
шают k. Например, если L = {abcda}, то Subseq2 (L) все подпоследовательности abcda, кроме
aa:

1. Решите задачу для k = 0, то есть для всех подслов.

2. Решите задачу для k = 1.

3. (*) Решите задачу для произвольного k.

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