ε-переходы и НКА-ε

ε-переход позволяет автомату сменить состояние, ничего не прочитав, — крошечное расширение, делающее сборку автоматов почти тривиальной.

ε-переход — переход НКА из одного состояния в другое без чтения входного символа; такой автомат называют НКА-ε.

Переход «бесплатно»

Обычный переход «съедает» символ входа. ε-переход — это переход по пустому слову ε: автомат может в любой момент проскользнуть по нему, не двигаясь по строке. Зачем? Чтобы склеивать автоматы. Если у вас есть автомат для языка A и автомат для языка B, то ε-переходы позволяют соединить их в автомат для A·B (конкатенация) или для A∪B (объединение) почти механически — просто протянув ε-стрелки между ними. Это сердце доказательства теоремы Клини, к которой мы придём.

ε-замыкание

Раз по ε можно ходить «бесплатно», то находясь в состоянии q, автомат фактически находится сразу во всех состояниях, достижимых из q по цепочкам ε-переходов. Это множество называют ε-замыканием (ECLOSE) состояния q. Симуляция НКА-ε работает так: (1) берём ε-замыкание стартового состояния; (2) на каждом символе делаем обычный переход, затем снова берём ε-замыкание результата; (3) в конце проверяем пересечение с принимающими.

Пример: НКА-ε для языка a*b*  («сколько-то a, потом сколько-то b»)

        a              b
       ┌─┐            ┌─┐
       │ v            │ v
  ──>((q0)) --ε-->   ((q1))

(q0): петля по a, ((q0)) принимающее (можно сразу b? нет — сначала ε)
ε-стрелка q0->q1 позволяет перейти к чтению b, не тратя символ.
ε-замыкание(q0) = {q0, q1}.

Симуляция НКА-ε на Python

Реализуем ε-замыкание (обход по ε-рёбрам) и общий прогон. Возьмём автомат для языка a*b*.

eps = {"q0": {"q1"}}                      # ε-переходы
delta = {("q0", "a"): {"q0"}, ("q1", "b"): {"q1"}}
accept = {"q1"}

def eclose(states):
    stack, seen = list(states), set(states)
    while stack:
        s = stack.pop()
        for t in eps.get(s, set()):
            if t not in seen:
                seen.add(t); stack.append(t)
    return seen

def run(word):
    cur = eclose({"q0"})
    for ch in word:
        nxt = set()
        for st in cur:
            nxt |= delta.get((st, ch), set())
        cur = eclose(nxt)
    return bool(cur & accept)

for w in ["", "aaa", "aabb", "bb", "ba"]:
    print(f"{w or 'ε':>4} -> {'принята' if run(w) else 'отвергнута'}")

Вывод:

   ε -> принята
 aaa -> принята
aabb -> принята
  bb -> принята
  ba -> отвергнута

«ba» отвергнута: после b нельзя вернуться к чтению a. ε-замыкание стартового состояния делает q1 принимающим сразу, поэтому пустая строка и «aaa» проходят.

Как работает под капотом

ε-переходы не добавляют мощности: любой НКА-ε преобразуется в обычный НКА (а затем в ДКА). Идея — «втянуть» ε-переходы в обычные: если из q можно по ε дойти до p, а из p по a — в r, то добавляем прямой переход q --a--> r и переносим принимающность по ε-замыканию. Поэтому НКА-ε, НКА и ДКА — три эквивалентных формализма для одного класса регулярных языков. ε-переходы — это «строительный клей», удобный при сборке, но устранимый.

Частые ошибки

Забыть ε-замыкание стартового состояния. Прогон начинается не с {q₀}, а с ECLOSE({q₀}) — иначе пропустите состояния, достижимые по ε сразу.

Не брать ε-замыкание после каждого символа. После обычного перехода всегда снова применяйте ECLOSE, иначе потеряете ветви.

Считать, что ε-переход что-то читает. Он не двигает указатель по строке — строка стоит на месте, меняется только состояние.

Итог

• ε-переход меняет состояние без чтения символа; автомат с ними — НКА-ε.
• ε-замыкание состояния — все состояния, достижимые по цепочкам ε-переходов.
• Симуляция: ε-замыкание старта, затем на каждом символе переход + повторное ε-замыкание.
• ε-переходы удобны для склейки автоматов (конкатенация, объединение), но мощности не добавляют.