Изменения

__TOC__

== 1. Автоматы и регулярные языки ==

## Добавить сюда определение гомоморфизма, образа и прообраза в соответствующий раздел, взять их [[Замкнутость регулярных языков относительно различных операций|отсюда]], оттуда соответственно, удалить их определения и сослаться на этот конспект. Еще лучше — создать

## В конспекте упоминается "свободный моноид", но не написано что это такое. Надо написать (в конспекте про моноид), и написать про то, какие еще бывают моноиды (кажется, это называется "моноид с порождающими соотношениями", но, может, говорят и "несвободный моноид"), поищите.

# [[Прямое произведение ДКА]]

## Вообще зачем такой короткий конспект нужен, не знаю, надо придумать, куда его запихать.

## Английские термины

## Англоязычные источники (хотя бы википедия)

# [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]

# [[Автоматы с eps-переходами. Eps-замыкание]]

## Опять классы языков курсивом

## Внутренние ссылки на автоматные и регулярные языки

## добавить ссылок на англоязычные источники, добавить в статью англоязычные термины

# [[Решение уравнений в регулярных выражениях]]

#: фиг знает что это, но надо написать, видимо

# [[Эквивалентность состояний ДКА]]

# [[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]

# [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]

## доказательство последнего утверждения

== 2. Контекстно-свободные грамматики ==

# [[Лемма о разрастании для КС-грамматик]]

# [[Лемма Огдена]]

## добавить английские термины

## добавить всякое интервики

# [[Автоматы с магазинной памятью]]

# [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]]

## Исправить оформление списков: нужно использовать либо точки, либо нумерацию числами/символами, но не оба способа одновременно.

## Картинка. Что она означает?

## ссылки на вики

## а зачем оно нужно?

## во-первых, теоремы именные, соответственно надо эти имена вписать (русские и английские)

## дать ссылки на английские источники и термины

# '''взяли''' [[Неразрешимость исчисления предикатов первого порядка]]

## написать. Это очень просто на самом деле, если немного помнить матлогику

## написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными.

# [[Теорема Райса-Шапиро]]