Контекстно-свободная грамматика, где # одного терминала равно разнице двух других - PullRequest
Новая
       17

Контекстно-свободная грамматика, где # одного терминала равно разнице двух других

0 голосов
/ 09 мая 2018

Язык определяется следующим образом:

L = {a ^ m b ^ n c ^ k | k = | m-n | }

Таким образом, за a следует b, а затем c, где число c является абсолютным значением минус b a.

Я не могу понять, как зафиксировать это поведение в CFG. Любой совет?

1 Ответ

0 голосов
/ 16 августа 2018

Исходя из предложения Криса Додда: 

L1 = {a^m b^n c^k | m >= n && k = m - n}
   = {a^m b^n c^k | m >= n && m = k + n}
   = {a^k a^n b^n c^k | m >= n}

Переставляя условие, мы преобразуем вычитание в сложение. Затем мы разделяем a^m, чтобы сделать структуру грамматики более понятной. Поэтому грамматика: 

S := aSc | X | e
X := aXb | e

Правило S обрабатывает внешнюю часть, а правило X - внутреннюю. 

L2 = {a^m b^n c^k | m < n && k = n - m}
   = {a^m b^n c^k | m < n && n = m + k}
   = {a^m b^m b^k c^k | m < n}

Аналогичная процедура, хотя структура немного отличается, и в итоге получается что-то вроде: 

S' := X'Y'
X' := aX'b | e
Y' := bY'c | e

Объединение их дает грамматику для союза: 

S   := S' | S''
S'  := aS'c | X | e
X   := aXb | e
S'' := X'Y'
X'  := aX'b | e
Y'  := bY'c | e
...