Найти контекст бесплатно грамматику для следующих - PullRequest
Новая
       16

Найти контекст бесплатно грамматику для следующих

0 голосов
/ 14 октября 2019

L = {a ^ nb ^ mc ^ k |n = m + 2k}

L = {wE (a, b) * | Na (w) + 2Nb (w)! = Nc (w)}

Найти контекстную грамматику дляследующее (правила производства)

1 Ответ

1 голос
/ 14 октября 2019

Для первого переписать это как L = {a ^ 2k a ^ mb ^ mc ^ k}. Обратите внимание, что мы можем строить строки извне, сначала требуя, чтобы два a добавлялись для каждого c, а затем, требуя дополнительного get, добавляемого для каждого b. 

S -> aaSc | T    // add two a to the front and one c to the back
T -> aTb | e     // add one a and one b to the middle

Для второго переписываемэто как объединение различных случаев:

  1. Na (w) + 2Nb (w)
  2. Na (w) + 2Nb (w)> Nc (w)

Мы можем начать с грамматики, где Na (w) + 2Nb (w) = Nc (w): 

S -> Sac | Sca | aSc | acS | caS | cSa | SS | T
T -> Tbcc | Tcbc | Tccb | TScc | bcTc | bccT | cTbc 
          | cTcb | cbTc | cbcT | ccTb | ccbT | TT | e

Для случая 1 нам нужно больше c. Мы можем изменить вышеприведенную грамматику следующим образом: 

S -> Sac | Sca | aSc | acS | caS | cSa | SS | T
T -> Tbcc | Tcbc | Tccb | bTcc | bcTc | bccT | cTbc 
          | cTcb | cbTc | cbcT | ccTb | ccbT | TT | C
C -> cC | c

Это гарантирует, что где-нибудь будет добавлено, по крайней мере, еще один c, и позволит добавить любое количество дополнительных c в любом месте. Для случая 2 нам нужно больше a или b. Мы можем изменить вышеуказанную грамматику следующим образом: 

S -> Sac | Sca | aSc | acS | caS | cSa | SS | T
T -> Tbcc | Tcbc | Tccb | bTcc | bcTc | bccT | cTbc 
          | cTcb | cbTc | cbcT | ccTb | ccbT | TT | C
C -> aC | bC | a | b

Это гарантирует, что где-нибудь будет добавлено по крайней мере еще одно a или b, и позволяет добавлять любое количество дополнительных a или b куда угодно.

...