Обычный язык

• Определение и свойства обычных языков

  • Обычные языки — это языки, которые распознаются конечными автоматами с постоянным числом состояний. 
  • Они включают все конечные языки, а также языки, которые могут быть описаны регулярными выражениями. 
  • Обычные языки не зависят от контекста, в отличие от контекстно-свободных языков. 

• Примеры и классификация

  • Примеры обычных языков включают строки с четным числом единиц и строки с нечетным числом единиц. 
  • Обычные языки могут быть классифицированы по различным критериям, таким как конечность, наличие звездочек и количество слов в языке. 

• Теоремы и сложности

  • Теорема Клини утверждает, что любой язык, который может быть описан регулярным выражением, является обычным. 
  • Класс REGULAR в теории сложности вычислений соответствует задачам, которые могут быть решены в постоянном пространстве. 
  • REGULAR не совпадает с AC0, но содержит некоторые нерегулярные языки. 

• Важность и подклассы

  • Обычные языки имеют важное место в иерархии Хомского и часто используются для доказательства нерегулярности других языков. 
  • Некоторые подклассы обычных языков включают конечные языки, языки без звездочек и языки с определенной длиной слов. 

• Обобщения и дальнейшие чтения

  • Понятие обычного языка было обобщено на бесконечные слова и деревья, а также на моноиды и распознаваемые множества. 
  • Для дальнейшего изучения можно обратиться к книге Филиппа Флайоле и Роберта Седжвика «Аналитическая комбинаторика» и к статье Клини «Представление событий в нейронных сетях и конечных автоматах».