Я как бы застрял с проблемой автомата и грамматики. Я много искал, но безуспешно.
Возможно ли вообще построить грамматику, порождающую этот язык L?
L = { a(2i) | i >= 0}
Может ли кто-нибудь предоставить мне простое решение?
построение грамматики языка a^(2^i)
Ответы (1)
Конечно, для этого языка можно написать грамматику, но это не будет контекстно-свободной грамматикой. Это легко продемонстрировать с помощью леммы о накачке.
Лемма о накачке утверждает, что для любого CFL существует некоторое целое число p такое, что любая строка s на языке, длина которой не меньше p, может быть записана как uvxyz, где u, v, x, y и z являются строками, а vy — нет. пусто, а для всех целых чисел n строка uvnxynz тоже есть в языке.
То есть для любой строки в языке (длина которой l больше p) существует некоторое k такое, что в языке есть строки длины l + nk для любого целого числа n. Это не относится к языку a2i, поскольку эти строки имеют экспоненциальную длину, поэтому язык не может быть контекстно-свободным.
Построить неконтекстно-свободную грамматику для языка не так сложно, но я не знаю, насколько это полезно.
Ниже приведена грамматика типа 0 (т. е. она также не зависит от контекста), но только из-за продукций, используемых для избавления от метасимволов. Основная идея здесь заключается в том, что мы помещаем начальный и конечный маркеры вокруг строки ([ и ]) и у нас есть «дупликатор» ( ), который перемещается слева направо, удваивая a; когда он достигает конечного маркера, он либо превращается в обратный шаттл (), либо съедает конечный маркер и превращается в начальный маркер-разрушитель ()
Start: [↣a]
↣a: aa↣
↣]: ↢]
↣]: ↞
a↢: ↢a
a↞: ↞a
[↢: [↣
[↞:
person
rici
schedule
16.04.2014
