Этот вопрос задавали в Gate 2009. Я не понимаю, как это не рекурсивно?как этот язык не рекурсивный?
L = {А м В м С А п В п | m, n ≥ 0}
L '= {A i B j C k | i, j, k ≥ 0}
Почему язык {L пересечение L '} не рекурсивный?
Поскольку «рекурсивная» является общей категорией языка, включающей все более простые классы языка, вопрос, вероятно, подразумевается под понятием, почему данный язык является чем-то более простым, чем рекурсивный язык. — говорят, что это тип 1, 2 или 3. в противном случае вопрос не имеет смысла (так как это явно рекурсивной.)
ответ можно найти, посмотрев на пересечении:
L ∩ L = {A м B m C | m ≥ 0}
Это всего лишь язык всех сбалансированных круглых скобок, за которым следует C, который может быть распознан детерминированным автоматом с отпиранием и, следовательно, является контекстно-свободным языком.
@Phrogz :) ну, я не знаю, как объяснить это более аккуратно .. –
Что такое 'A',' B' и 'C'? – user2357112
Какая грамматика это? PEG? BNF? Что такое «Gate 2009» и как он относится к этому вопросу? Простое пометка этого с помощью «автоматов», по-видимому, недостаточно для того, чтобы кто-то понял контекст, в котором вы задаете этот вопрос. – Phrogz