Кратко основные формулы

$$ a^* = \lambda \space ∪ \space a^* a $$

$$ (a^b^)^* = (a \space ∪ \space b)^* $$

$$ (cb^)^ = \lambda ∪ c(c \space ∪ \space b)^* $$

Что нам мешает и как надо упрощать выражение

Что в этих проблемах общее

• Проблема: нам что-то мешает построить автомат.
• Решение — расписать кейсы (обычно два): когда пустое слово, а когда берём один раз.

Case 1: ab

Надо сначала сколько угодно раз взять а, а потом сколько угодно б (в том числе ноль раз). Автоматом это фиг нарисуете.

Solution for ab

Вспомним формулу:

$$ a^* = \lambda \space ∪ \space a^* a $$

Заменяем это вот такой штукой, перемножаем скобку на букву перед ней и красота.

Case 2: (cb*)*

Solution

$$ (cb^)^ = \lambda ∪ c(c \space ∪ \space b)^* $$

Case 3: (ab)*

Solution

$$ (a^b^)^* = (a \space ∪ \space b)^* $$