а) Почти справа ...
Эта грамматика генерирует ровно набор строк, составленных из сбалансированных скобок.Чтобы понять, почему это так, давайте попробуем сделать быструю демонстрацию.
Во-первых: все, что выходит из вашей грамматики, является строкой со сбалансированными скобками.Почему ?, простая индукция:
- Epsilon - строка сбалансированных (пустых) скобок.
- если A - строка сбалансированных скобок, (A) также сбалансирован.
- если А1 и А2 сбалансированы, то же самое относится и к А1А2 (я использую слишком разные идентификаторы просто для того, чтобы четко указать, что А -> АА не обязательно производит одинаковое для каждого А).
Второе: каждый набор сбалансированных строк создается вашей грамматикой.Давайте сделаем это по индукции для размера строки.
- Если строка имеет нулевой размер, это должно быть значение Epsilon.
- Если нет, то N равно размеру строки.string и M - длина самого короткого префикса, который сбалансирован (обратите внимание, что остаток строки также сбалансирован):
- Если M = N, вы можете создать эту строку с (A).
- Если M AA, первые M символов с первым A и последним N - M с последним A. В любом случае вы должны создать строку короче, чем N символов,так что по индукции вы можете сделать это.QED.
Например: (() ()) (())
Мы можем сгенерировать эту строку, используя именно идею демонстрации.
A -> AA -> (A) A -> (AA) A -> ((A) (A)) A -> (() ()) A -> (() ()) (A) -> (() ()) ((A)) -> (() ()) (())
b) Конечно, рекурсии влево и вправо достаточно, чтобы сказать, что она неоднозначна, но длячтобы понять, почему эта грамматика является неоднозначной, следуйте той же идее для демонстрации:
Она неоднозначна, потому что вам не нужно брать самый короткий сбалансированный префикс.Вы можете взять самый длинный сбалансированный (или вообще любой сбалансированный префикс), который не соответствует размеру строки, и демонстрация (и генерация) будут следовать тому же процессу.
Пример: (()) () ()
Вы можете выбрать A -> AA и сгенерировать с первой A подстроку (()) или подстроку (()) ().