Теореми и следствия за контролно 1

Question 1

Теорема и следствие на Майхил-Нероуд за регулярни езици

Answer 1

Ако L е регулярен език, съществува детерминиран автомат с толкова състояния, колкото са класовете на еквивалентност на ≡_L. Следствие: L е регулярен ⇔ ≡_L има краен брой класове.

Question 2

Лема за разрастването за регулярни езици

Answer 2

За регулярен език L съществува число p, такова че всяка дума w ∈ L с |w| ≥ p може да се раздели на xyz, така че |xy| ≤ p, |y| > 0 и ∀i ≥ 0: xy^i z ∈ L.

Question 3

Детерминизация

Answer 3

Сложността на детерминизацията (преобразуване от НКА в ДКА) е експоненциална спрямо броя на състоянията.

Question 4

Автомат по регулярен израз

Answer 4

Конструкция на автомат от регулярен израз може да се извърши с полиномиална сложност.

Question 5

Регулярен израз по краен автомат

Answer 5

Преобразуване на краен автомат в регулярен израз е с експоненциална сложност.

Question 6

Минимизация

Answer 6

Минимизацията на краен детерминиран автомат се извършва с полиномиална сложност.

Question 7

Дали два детерминирани автомата са еквивалентни

Answer 7

Проверка дали два детерминирани автомата разпознават един и същ език може да се извърши с полиномиална сложност.

Question 8

Дали два недетерминирани автомата са еквивалентни

Answer 8

Проверка дали два недетерминирани автомата са еквивалентни е с експоненциална сложност.