Определение не зависящего от контекста грамматики для конкретного языка

Question

Определение не зависящего от контекста грамматики для конкретного языка

У меня есть язык, в котором каждая строка в этом языке имеет четное количество 0 как 1 (например, 0101, 1010, 1100, 0011, 10 все на языке). Я надеялся определить грамматику без контекста, которая описывает этот язык. После определения грамматики без контекста я хочу официально доказать, что эта грамматика без контекста описывает этот язык.

Я придумал контекстно-свободные правила производства грамматики:

    S->0S1S
    S->1S0S
    S->ε

Это правильная контекстно-свободная грамматика для определения этого языка?

Я немного озадачен для доказывающей части. Я предполагаю, что мне понадобится какая-то индукция?

0

parsing context-free-grammar computation-theory context-free-language

Источник

user3430675 17 мар '14 в 21:12

1 ответ

Решение

Другие вопросы по тегам parsing context-free-grammar computation-theory context-free-language

user1516456 17 мар '14 в 22:07 2014-03-17 22:07 · Accepted Answer · 2014-03-17 22:07

Эта грамматика выглядит правильно для меня.

Я бы доказать это, показав оба направления (то есть строка на языке, если она производится грамматикой).

Доказать, что все строки, производимые грамматикой, написаны на языке, легко: просто учтите, что все произведения грамматики выдают одинаковые числа 1 и 0. Поэтому любая комбинация произведений должна создавать строку на языке.

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

Удачи