Две разные грамматики для одного набора выходов

Question

Можете ли вы дать мне 2 разные грамматики, которые выводят один и тот же набор слов?

Иллюстрация:

Учитывая грамматику A и B над алфавитом {0,1}, если грамматика Aможет произвести слово 0101001, грамматика B также может.Если грамматика B может произвести 0101111, то грамматика A может также.И если грамматика A не может произвести 01001, то и B не может.

Но дело здесь в том, что грамматика A и B отличаются друг от друга, то есть они используют совершенно разные алгоритмы.Тогда набор выходов, которые они производят, является не просто правильным подмножеством другого.То есть их соответствующий набор выходов должен иметь одинаковую мощность.Возможно, они разного уровня сложности, но это не имеет значения.Если вы можете, я был бы очень признателен, если бы вы дали мне грамматику по алфавиту {0,1}, как классическая машина Тьюринга.

Answer 1

Не уверен, что это возможно.Если A может производить вывод a, то либо B содержит непосредственно a, либо содержит b и b 'короче, чем a, генерирующий a.Затем тот же аргумент применяется к b (и b ') - либо в A непосредственно, либо в a существует корень a и a, который порождает b.Повторяйте этот аргумент, и в итоге вы получите точку, где отдельные элементы имеют длину 1, поэтому вы не сможете разбить их дальше, и у вас должны быть одинаковые элементы как в A, так и в B.

Answer 2

Это трюк в порядке?Строки типа 0*n1*m (например, 000000111) можно построить слева направо:

A
A -> 0A
A -> B
B -> 1B
B -> {}

справа налево:

B
B -> B1
B -> A
A -> A0
A -> {}

от середины:

AB
A -> A0
A -> {}
B -> 1B
B -> {}