Поиск контекстно-свободной грамматики для данного языка

Question

Я пытаюсь найти CFG для языка A ниже.

Я потратил часы на это, но все еще не мог найти ответ. Мне также пришла в голову мысль, что это может не быть контекстно-свободным языком, но на самом деле есть КПК, который его распознает.

Буду очень признателен, если кто-нибудь сможет мне помочь с этим.

  A={0^a 1^b 0^c 1^d| a+b < c+d, a,b,c,d>=1}

Answer 1

Хороший способ справиться с такими неравенствами - начать с грамматики равенства, а затем добавить один или несколько дополнительных символов.

Вот более простой пример, с которого можно начать. Давайте посмотрим на язык

L = {0<sup>a</sup>1<sup>b</sup>0<sup>c</sup> | a+b < c, a,b,c &ge; 1}

Мы начнем с языка, где соотношение длин равно:

L' = {0<sup>a</sup>1<sup>b</sup>0<sup>c'</sup> | a+b = c', a,b,c' &ge; 1}

Теперь должно быть ясно, что

L = {&omega; 0<sup>c"</sup>|&omega; &in; L', c" &ge; 1}

Другими словами, L состоит из строки из L', за которой следует один или несколько нулей. Оригинал c был разбит на c' + c".

Написать грамматику для L просто: L':

L ⇒ L' 0
L ⇒ L 0

Или, если вы предпочитаете:

L ⇒ L' Z
Z ⇒ 0  
Z ⇒ Z 0  

Так что теперь нам просто нужно поработать над L'. Так как мы знаем, что c' = a + b, мы можем заменить 0<sup>c'</sup> на 0<sup>b</sup>0<sup>a</sup>, давая нам:

L' = {0<sup>a</sup>1<sup>b</sup>0<sup>b</sup>0<sup>a</sup> | a,b &ge; 1}

Это, как выяснилось, является комбинацией внутреннего языка с тем же числом 1 и 0,в окружении равного числа ведущих и конечных 0. Другими словами:

L' ⇒ 0 M 0
L' ⇒ 0 L' 0 
M ⇒ 1 0
M ⇒ 1 M 0

Это делает вас на полпути. Удачи с оригинальным вопросом.