Неограниченная грамматика: { sss | s существует в {a,b}* }

Question

Как можно построить неограниченную грамматику для sss? Я знаю, что для того, чтобы построить ss, вам нужно создать ss^r и затем перевернуть вторую строку, но как это сделать для sss?

Answer 1

В этом может быть несколько ошибок, но идея должна привести вас на правильный путь.

// section 1
S := LTR
T := ATWX | BTYZ | N

// section 2
WW' := W'W
WY' := Y'W
YW' := W'Y
YY' := Y'Y

// section 3
WX' := W'X'
WZ' := W'Z'
YX' := Y'X'
YZ' := Y'Z'

// section 4
XW' := W'X
XX' := X'X
XY' := Y'X
XZ' := Z'X
ZW' := W'Z
ZX' := X'Z
ZY' := Y'Z
ZZ' := Z'Z

// section 5
XR  := X'R
ZR  := Z'R

// section 6
NW' := W'N
NX' := X'N
NY' := Y'N
NZ' := Z'N
NR  := Q

// section 7
AQ  := Qa
W'Q := Qa
X'Q := Qa
BQ  := Qb
Y'Q := Qb
Z'Q := Qb
LQ  := e

В разделе 1 изложена основная схема. Мы собираемся отметить начало и конец нашего рабочего пространства L и R, чтобы быть совершенно явными. T - наше рабочее пространство, а L и R - левый и правый маркеры. Наше рабочее пространство может добавить либо три as (это то, что A, W и X станут позже) или добавить три bs (это то, чем B, Y и Z станут позже), или он может выйти, генерируя специальный нетерминальный N. N будет тем, что превращает нашу цепочку нетерминалов в цепочку терминалов, как мы увидим позже.

Итак, нам нужно xxx за x в (a+b)*, A а также B добавить в конец первого x из-за того, как мы организовали производство. Работа раздела 2 состоит в том, чтобы убедиться, что W а также Y добавить в конец второго x, К сожалению, наши постановки ставят W а также Y в начале второго x так что без коррекции мы бы в итоге xx^R, Раздел 2 исправляет эту проблему, "плавая" W а также Y вправо, пока они находятся слева от W или же Y это уже нашло свое место. Wс и YОни не могут обгонять друг друга, и это гарантирует, что они остановятся в правильной последовательности, как только музыка остановится.

Раздел 3 показывает, как символы во втором появлении x найти их правильные позиции. По сути, они движутся вправо (на основании раздела 2), пока не найдут символы третьего x которые находятся на своих местах. Так как символы второго x имеют свое место перед символами третьего xпоследний возможный прямо перед любым символом третьего x (X или же Z) является правильной позицией для каждого символа второго x, Таким образом, мы плывем прямо до конца второго x,

Мы повторяем процесс для третьего x в разделе 4, хотя мы должны позволить этим символам (X а также Z) проплыть мимо всех символов второго или третьего x которые уже нашли свои места. Эти символы не могут проходить сами, поэтому по той же логике, что и в разделе 2, мы получим символы в правильной последовательности.

Раздел 5 говорит, когда нужно останавливать плавающие символы, которые составляют третий x направо. Помните конец маркера рабочего пространства R? Последний символ третьего x происходит полностью справа, прямо перед R, И вот тогда мы узнаем, что нашли правильное место для символа.

Раздел 6 начинает процесс завершения нашего деривации. У нас есть прекрасная цепочка нетерминалов, и мы хотим превратить их в терминалы. Первое, что мы делаем, это плавающие N направо мимо удачно расположенных символов второго и третьего xдо конца строки маркера R, Нам не нужны R для чего угодно, поэтому мы преобразуем N в Q, Как мы увидим в следующем разделе Q это то, что заставляет волшебство случиться.

Раздел 7 описывает, как Q плавает влево через всю цепочку нетерминалов, которые нашли свое место вплоть до L, изменяя нетерминалы на соответствующий терминал по пути. Как только он находит L, он стирает оба нетерминала, оставляя за собой только строку конечных символов. Вывод завершен.

Чтобы проиллюстрировать процесс, давайте сгенерируем aabaabaab,

S
-> LTR 
-> LATWXR 
-> LAATWXWXR 
-> LAABTYZWXWXR
-> LAABNYZWXWXR
-> LAABNYZWXWX'R
-> LAABNYZWXW'X'R
-> LAABNYZWW'XX'R
-> LAABNYZWW'X'XR
-> LAABNYZWW'X'X'R
-> LAABNYZW'WX'X'R
-> LAABNYZW'W'X'X'R
-> LAABNYW'ZW'X'X'R
-> LAABNYW'W'ZX'X'R
-> LAABNYW'W'X'ZX'R
-> LAABNYW'W'X'X'ZR
-> LAABNYW'W'X'X'Z'R
-> LAABNW'YW'X'X'Z'R
-> LAABNW'W'YX'X'Z'R
-> LAABNW'W'Y'X'X'Z'R
-> LAABW'NW'Y'X'X'Z'R
-> LAABW'W'NY'X'X'Z'R
-> LAABW'W'Y'NX'X'Z'R
-> LAABW'W'Y'X'NX'Z'R
-> LAABW'W'Y'X'X'NZ'R
-> LAABW'W'Y'X'X'Z'NR
-> LAABW'W'Y'X'X'Z'Q
-> LAABW'W'Y'X'X'Qb
-> LAABW'W'Y'X'Qab
-> LAABW'W'Y'Qaab
-> LAABW'W'Qbaab
-> LAABW'Qabaab
-> LAABQaabaab
-> LAAQbaabaab
-> LAQabaabaab
-> LQaabaabaab
-> aabaabaab