При рассмотрении компьютерных моделей вычислений иерархия Хомского обычно характеризуется (по порядку) конечными автоматами, автоматами со спуском, линейными связанными автоматами и машинами Тьюринга. Для первого и последнего уровней 1 (обычные языки и рекурсивно перечислимые языки) не имеет...
Я просматривал определение контекстно-зависимого языка в Википедии и обнаружил следующее: Каждая категория языков является надлежащим подмножеством категории прямо над ней. Любой автомат и любая грамматика в каждой категории имеют эквивалентный автомат или грамматику в категории непосредственно над...
Я пытаюсь понять контекстно-зависимые грамматики. Я понимаю, почему языки как { w w ∣ w ∈ A*}{ww∣w∈A∗}\{ww \mid w \in A^*\} {anbncn∣n∈N}{anbncn∣n∈N}\{a^n b^n c^n \mid n\in\mathbb{N}\} не являются контекстно-свободными, но я хотел бы знать, чувствителен ли контекстный язык, похожий на...
На самом деле я обнаружил, что набор контекстно-зависимых языков, ( принятых языков) не так широко обсуждается, как (обычные языки) или (контекстно-свободные языки). А также открытая проблема не так известна, как «аналогичная» проблема: « ".CSLCSL\mathbf{CSL}R E G C F L D S P A C E ( O ( n ) ) = ?...
Я ищу контекстно-зависимую грамматику, которая описывает следующий язык: .L = { w w ∣ w ∈ { a , b }*, | ш |≥ 1 }Lзнак равно{весвес|вес∈{a,б}*,|вес|≥1}L = \{ ww \mid w ∈ \{a,b\}^{\ast}, |w| ≥ 1\} У меня проблемы с тем, что никакие правила, такие как не разрешены, и поэтому я не могу поместить...