Может ли обычный язык иметь линейный ограниченный автомат
Как говорится в вопросе:
Я пытаюсь понять автоматы. Может ли каждый регулярный язык иметь линейный ограниченный автомат?
1 ответ
Решение
Да, возможно иметь линейно ограниченные автоматы для каждого обычного языка. Обычные языки являются подходящим подмножеством контекстно-зависимых языков. CSL - это язык, связанный с линейными ограниченными автоматами (LBA). Для получения дополнительной информации об иерархии классов формальных грамматик и языков читайте о Chomsky Hierarchy,