Чт. Апр 18th, 2024

Пусть формальная грамматика задается последующим образом: T = {а, b} (т.е. огромное количество терминальных знаков — алфавит языка — состоит из 2-ух знаков — а и b); N = {S}, т.е. огромное количество нетерминальных знаков состоит из единственного знака S — он, естественно, оказывается выделенным; система подстановок пусть имеет последующий вид: SaSa, SbSb, S→ a, Sb

Описанная грамматика порождает язык, состоящий из всех «слов-перевертышей» в алфавите {а, b}, имеющих нечетную длину, т.е. слов, которые слева вправо читаются также, как справа влево, к примеру, aba, abababa, bbbbb, baaaaaab и т.д. Просто созидать, что применение первых 2-ух правил (в любом числе и хоть какой последовательности) порождает цепочки (слова) типа αSα-1, где α-1 значит слово α, записанное справа влево; применение третьего и 4-ого правил завершает процесс порождения слова и сформировывают слова типа αаα1 либо αbα-1 .

От content

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *