Как мне сделать это даже? L = {w ∈ {0, 1} * | n0 (w) = 2n1 (w) и | w | даже} - PullRequest
Новая
       23

Как мне сделать это даже? L = {w ∈ {0, 1} * | n0 (w) = 2n1 (w) и | w | даже}

0 голосов
/ 29 марта 2019

Как мне сделать CFG для этого языка?У меня есть S -> S1S0S0 |S0S1S0S |S0S0S1S |Эпсилон, но я не уверен, как это сделать даже в длину.

1 Ответ

0 голосов
/ 30 марта 2019

Грамматика, которая игнорирует ограничение, что | w | быть четным: 

S -> 00S1 | 0S01 | S001 | 010S | 01S0 | 0S10 | S010 | 100S | 10S0 | 1S00 | S100
S -> SS
S -> epsilon

Как мы можем заставить это | w | быть даже? Ну, мы можем ввести новый символ T для обработки случая, когда | w | нечетно и просто не позволяет T производить эпсилон. 

S -> 001T | 00T1 | 0T01 | T001 | 010T | 01T0 | 0T10 | T010 | 100T | 10T0 | 1T00 | T100
S -> SS | TT
S -> epsilon
T -> 001S | 00S1 | 0S01 | S001 | 010S | 01S0 | 0S10 | S010 | 100S | 10S0 | 1S00 | S100
T -> ST | TS

Почему это работает? Поскольку, если S генерирует строки четной длины, а T генерирует строки нечетной длины, эти произведения сохраняют это свойство и учитывают все способы перехода от строк четной к нечетной длине. Поскольку мы не хотим принимать строки нечетной длины, мы не позволяем исключить T. Мы можем получить 000011: 

S -> 00T1 -> 0000S11 -> 000011

Но мы не можем получить 000000111: 

S -> 00T1 -> 0000S11 -> 000000T111 -> …?

Та же самая базовая идея будет работать и с вашей грамматикой, но я оставляю это как упражнение, поскольку наша грамматика имеет больше S на строку и потребует большого количества производств для учета комбинаций S и T, которые дают четные длины.

...