Оглавление
Обычный язык
-
Определение и свойства обычных языков
- Обычные языки – это языки, которые распознаются конечными автоматами с постоянным числом состояний.
- Они включают все конечные языки, а также языки, которые могут быть описаны регулярными выражениями.
- Обычные языки не зависят от контекста, в отличие от контекстно-свободных языков.
-
Примеры и классификация
- Примеры обычных языков включают строки с четным числом единиц и строки с нечетным числом единиц.
- Обычные языки могут быть классифицированы по различным критериям, таким как конечность, наличие звездочек и количество слов в языке.
-
Теоремы и сложности
- Теорема Клини утверждает, что любой язык, который может быть описан регулярным выражением, является обычным.
- Класс REGULAR в теории сложности вычислений соответствует задачам, которые могут быть решены в постоянном пространстве.
- REGULAR не совпадает с AC0, но содержит некоторые нерегулярные языки.
-
Важность и подклассы
- Обычные языки имеют важное место в иерархии Хомского и часто используются для доказательства нерегулярности других языков.
- Некоторые подклассы обычных языков включают конечные языки, языки без звездочек и языки с определенной длиной слов.
-
Обобщения и дальнейшие чтения
- Понятие обычного языка было обобщено на бесконечные слова и деревья, а также на моноиды и распознаваемые множества.
- Для дальнейшего изучения можно обратиться к книге Филиппа Флайоле и Роберта Седжвика “Аналитическая комбинаторика” и к статье Клини “Представление событий в нейронных сетях и конечных автоматах”.
Полный текст статьи: