Как я могу показать, что этот язык не зависит от контекста, создавая грамматику без контекста?

Question

Как я могу построить контекстную грамматику для следующего языка:

L = {0 ^ n1 ^ nx | n> = 1 и x ∈ {0, 1} *}

Этот язык состоит в том, что за некоторым числом нулей следует такое же количество единиц, что и некоторое количество битовых строк. Я думал, что мне нужно S -> 0S1 для части 0 ^ n1 ^ n и A -> 0A | 1А | e для x ∈ {0, 1} *. Поскольку мне нужно несколько битовых строк после одинакового количества нулей и единиц, я сделал

S -> 0S1A | e

A -> 0A | 1А | e

Но грамматика принимает 0001101, что неверно. Есть 3 0 и только 2 1. Я новичок в CFG. Может кто-нибудь дать мне совет по этому языку?

Answer 1

Всякий раз, когда у вас есть язык, который можно разложить на конкатенацию двух подъязыков, создайте два языка по отдельности, а затем объедините их:

S → A B
A → …
B → …

В этом случае A будет 0 ⁿ 1 ⁿ и B будет {0, 1} ^*.