Записки по ЕАИ
Дефиниция и основни свойства
Конструкция на автомат по даден език
Затвореност относно сечение, обединение, разлика
Пример за доказателство, че даден автомат описва точно конкретен език
Дефиниция и основни свойства
Еквивалентност с детерминираните автомати - един пример е достатъчен
Затвореност относно сечение, обединение, разлика - да се обясни само с примери
Дефиниция
Еквивалентност на регулярните и автоматните езици
Релация на Майхил-Нероуд
Критерий за регулярност на език
Конструкция на минимален автомат по даден регулярен език
Алгоритъм за минимизация на автомат
Лемата за покачването
Пример, че тя дава само необходимо, но не и достатъчно условие
Примери за безконтекстни граматики и безконтекстни езици
Всеки автоматен език е безконтекстен
Затвореност относно обединение, конкатенация, звезда на Клини
Конструкция на граматика по даден език
Еквивалентност с безконтекстните езици
Безконтекстните езици не са затворени относно сечение и разлика