如何显示给定语言是明确的

Question

给出以下语法：

$$ begin{align} S rightarrow &A1B A rightarrow & 0A mid varepsilon B rightarrow & 0B mid 1B mid varepsilon end{align} $$

我如何表明这种语法是明确的？我需要找到一种模棱两可的语言的语法，并证明它。

我知道我是否被要求证明该语言是模棱两可的，那么我应该为同一字符串找到两种不同的解析树，但我不知道该怎么办。

Answer 1

要显示语法是明确的，您必须争辩说，对于语言中的每个字符串，只有一个衍生树。

在这种特殊情况下，您可以观察到$ a $仅生成$ 0 $的s，因此启动符号$ s $生成的$ 1 $必须是字符串中的第一个$ 1 $。

任何语法都可以通过将$ s 等链条制作添加到s $中来模棱两可。

Answer 2

该语法等效于$$ begin {align} s rightArrow＆0a1b mid 1b a rightarrow＆rightarrow＆0a mid mid varepsilon b b rightArrow＆rightArrow＆rightArrow＆0b mid 1b mid 1b mid mid varepsilon varepsilon endign } $$等等 喜欢 一种简单的语法，我们可以证明这种语法不明确。当然，这种语法并不简单。