Я уверен, что у меня есть один, но он имеет 42 правила построения и не очень хорошо обобщает. Как я могу это сделать с меньшим количеством правил построения?Нужна грамматика без контекста, в которой в 5 раз больше одного символа, чем у другого
Язык {a, b} *, где число a в пять раз больше числа b.
Я знаю, что для языка {a^n (concatenate) b^m; m = 5n} это было бы просто
S = aSbbbbb | λ
Но когда персонажи могут быть в любом порядке, я теряюсь.
Прежде всего, обратите внимание, что если предложение имеет в 5 раз больше символов, чем другое, оно всегда будет выглядеть примерно как aaabaabaaaaa. Таким образом, одно предложение может быть aaaaab или aaabaa. Другое замечание состоит в том, что всякий раз, когда мы добавляем b, мы должны добавить пять символов a.
Следующая грамматика действительно имеет в пять раз больше a символов как b символов:
S = AS | λ
A = Baaaaa | aBaaaa | aaBaaa | aaaBaa | aaaaBa | aaaaaB
B = bS | Sb
Мы начинаем с S, который может либо пустым (что удовлетворяет требованию) или A.
Правило для A составляет не менее 5 a символов и B. Теперь для B мы можем либо разместить b и остановиться там (выбирая пустую строку для S), либо путем повторного запуска (выбрав A для S). Это гарантирует, что мы всегда помещаем в 5 раз больше a символов в виде b символов.
Наконец, эта грамматика может быть легко обобщена на грамматику, чем должно содержать n раз больше символов одного, чем другого (путем простого расширения правила A).
Я не знаю, что вы только что сказали, но вы использовали персонажа, которого я не знаю, как делать с клавиатурой, поэтому он должен быть прав. +1;) – hvgotcodes
Спасибо за ответ! Но я не уверен, что это правильно. Я не могу найти способ получить, например, baaaaaaaaaab из этих правил. Приношу свои извинения, если я что-то пропускаю. Вы видите способ получить baaaaaaaaaab? Кажется, только можно получить b на одном конце строки. – Aurast
Вы правы, я не мог найти способ получить либо 'baaaaaaaaaab'. Я скорректировал правило для 'S', чтобы сделать это возможным:' S' = 'AS' =' AAS' = 'AA' =' BaaaaaA' = 'BaaaaaaaaaaB' =' bSaaaaaaaaaaB' = 'bSaaaaaaaaaabS' =' bSaaaaaaaaaab' = 'baaaaaaaaaab'. –
У вас есть доказательства того, что можно выразить грамматику несколькими правилами? –