Как показать, что данный язык однозначно

Question

Дано следующая грамматика:

$$ begin {Align} s rightRrow & a1b a rightRrow & 0a mid varepsilon b rightarrow & 0b mid 1b mid varepsilon end {align} $$

Как я могу показать, что эта грамматика однозначна? Мне нужно найти грамматику для того же языка, который неоднозначен, и продемонстрировать ее.

Я знаю, если бы меня попросили доказать, что язык является амбициозным, я должен найти два разных деревья разбора для той же строки, но я не знаю, что делать.

Answer 1

Показывать грамматикой однозначно, вы должны утверждать, что для каждой строки на языке есть только одно дерево выводов.

В этом конкретном случае вы можете наблюдать, что $ a $ приносит только $ 0 $, поэтому $ 1 $, генерируемый START Symbol $ S $, должен быть первым $ 1 $ в строке.

Любая грамматика может быть сделана неоднозначной, добавляя сетевые производства, такие как $ s to s $.

Answer 2

Эта грамматика эквивалентна с $$ begin {align} s rightarrow & 0a1b mid 1b a rightorrow & 0a mid varepsilon b rightorrow & 0b mid 1b mid varepsilon end {align } $$ и так как Простая грамматика мы можем показать, что эта грамматика не является неоднозначной. Конечно, эта грамматика не проста.