Формальные языки 2015 — различия между версиями

Материал из SEWiki
Перейти к: навигация, поиск
Строка 22: Строка 22:
 
1) Опишите ДКА, который распознает следующее множество слов над алфавитом {0, 1}:
 
1) Опишите ДКА, который распознает следующее множество слов над алфавитом {0, 1}:
  
a) множество слов, содержащих подстроку 011;
+
a) множество слов, содержащих подстроку «011»;
  
b) множество слов, начинающихся или заканчивающихся (или и то, и другое) на 01;
+
b) множество слов, начинающихся или заканчивающихся (или и то, и другое) на «01»;
  
 
c) множество слов, в которых нет пяти одинаковых цифр подряд.
 
c) множество слов, в которых нет пяти одинаковых цифр подряд.
Строка 32: Строка 32:
 
a) множество слов, в которых содержатся два нуля, число символов между которыми делится на 3;
 
a) множество слов, в которых содержатся два нуля, число символов между которыми делится на 3;
  
b) множество слов, состоящих либо из повторяющихся несколько раз (один или более) строчек 01, либо из повторяющихся несколько раз (один или более) строчек 010;
+
b) множество слов, состоящих либо из повторяющихся несколько раз (один или более) строчек «01», либо из повторяющихся несколько раз (один или более) строчек «010»;
  
c) множество слов, в которых на одной из трех левых или двух правых позиций стоит 1;
+
c) множество слов, в которых на одной из трех левых или двух правых позиций стоит единица;
  
 
3) Детерминизируйте автомат, являющийся ответом на задание 2b.
 
3) Детерминизируйте автомат, являющийся ответом на задание 2b.

Версия 02:02, 24 февраля 2015

Лектор — Михаил Эдуардович Дворкин (mikhail.dvorkin@gmail.com)

Практика — Михаил Эдуардович Дворкин

Важная книга для первой части курса: Хопкрофт, Мотвани, Ульман. Введение в теорию автоматов, языков и вычислений.

План

Лекция 1

  • Языки и yes/no-задачи. Теоретико-множественное невозможность описания языков.
  • Детерминированные конечные автоматы. Принятие слова.
  • Эквивалентность состояний. Минимизация ДКА.
  • Правые контексты.

Лекция 2

  • Динамическое программирование по ДКА.
  • Прямое произведение ДКА.
  • Недетерминированные конечные автоматы с eps-переходами. Принятие слова.
  • Детерминизация НКА.

Д/з №1, срок сдачи: 3 марта 2015 г., 14:10

1) Опишите ДКА, который распознает следующее множество слов над алфавитом {0, 1}:

a) множество слов, содержащих подстроку «011»;

b) множество слов, начинающихся или заканчивающихся (или и то, и другое) на «01»;

c) множество слов, в которых нет пяти одинаковых цифр подряд.

2) Опишите HКА или ε-НКА, который распознает следующее множество слов над алфавитом {0, 1}:

a) множество слов, в которых содержатся два нуля, число символов между которыми делится на 3;

b) множество слов, состоящих либо из повторяющихся несколько раз (один или более) строчек «01», либо из повторяющихся несколько раз (один или более) строчек «010»;

c) множество слов, в которых на одной из трех левых или двух правых позиций стоит единица;

3) Детерминизируйте автомат, являющийся ответом на задание 2b.

4) ... и минимизируйте результат выполнения задания 3.